WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Re: Een kansverdeling

Dit is een reactie op vraag 73105

U schrijft op het einde:

De betrekkingen worden bij stijgende aantallen a's wat ingewikkelder maar het lijkt me allemaal wel te doen.

Zoudt U het niet erg vinden om dat voor mij te doen. Ik heb het nodig voor een wetenschappelijk artikel en wil graag U naam noemen als auteur van de verdeling. Een andere mogelijkheid is dat U mij laat zien hoe het werkt in een eenvoudiger geval:

Rijen letters van lengte 6 bestaande uit de letters a, b en c (met gelijke kansen), die voldoen aan (1) a komt ten minste eenmaal voor en (2) opeenvolgende letters zijn verschillend.

Het wetenschappelijke artikel is een vervolg op een eerder artikel, dat ik, als U wil, aan U op kan sturen.
Ad van
Iets anders - donderdag 29 mei 2014

Antwoord

We bekijken woorden in het alphabet $\{a,b,c,d,e,f\}$.

We noteren met $W_n$ de verzameling van woorden van lengte $n$,
dan geldt natuurlijk $|W_n|=6^n$.

De belangrijke verzameling is
$V_n=\{w\in W_n:(\forall i$<$n)(w_i\neq w_{i+1})\}$, de woorden
waarin opeenvolgende letters altijd verschillen.
Er geldt $|V_n|=6\times5^{n-1}$.

Dat is makkelijk met inductie te bewijzen: het geval $n=1$
is makkelijk: $|V_1|=6$.
Voor grotere $n$ verdelen we $V_n$ in zes even grote stukken:
$V_{n,t}=\{w\in V_n:w_n=t\}$, met $t\in\{a,b,c,d,e,f\}$.
Dat deze stukken even groot zijn volgt coördinaatsgewijs de permutatie
$a\to b\to c\to d\to e\to f\to a$ toe te passen.
Nu volgt
$$
|V_{n+1}|=6\times|V_{n+1,a}|=6\times5\times|V_{n,b}|=
6\times5\times\frac16|V_n|=5\times|V_n|
$$

Voor elke $k$ en $n$ noteren we
$$
U_{k,n}=\{w\in V_n:|\{i:w_i=a\}|=k\}
$$
Voor de kansen waar naar gevraagd werd geldt dan
$$
P(X=k)= \frac{|U_{k,n}|}{|V_n|-|U_{0,n}|}
$$
waarbij $n=18$ en $k=1, \dots, 9$.

Om de $|U_{k,n}|$ te bepalen noteren we, voor $t\in\{a,b,c,d,e,f\}$,
$$
U_{k,n,t}=\{w\in U_{k,n}: w_n=t\}
$$
Dan geldt dus
$$
|U_{k,n}|=\sum\bigl\{|U_{k,n,t}|:t=a,b,c,d,e,f\bigr\}
$$
Verder geldt, voor $s,t\in\{b,c,d,e,f\}$, dat
$|U_{k,n,s}|=|U_{k,n,t}|$.

Conclusie:
$$
|U_{k,n}|=|U_{k,n,a}|+5\times|U_{k,n,b}|
$$
We gaan $|U_{k,n,b}|$ en $|U_{k,n,a}|$ bepalen.
We schrijven $ua(k,n)=|U_{k,n,a}|$ en $ub(k,n)=|U_{k,n,b}|$.

We hebben
$$
U_{k,n+1,a}=\bigcup\{U_{k-1,n,t}\times\{a\}:t=b,c,d,e,f\}
$$
en
$$
U(k,n+1,b)=(U(k,n,a)\times\{b\})\cup
\bigcup\{U(k,n,t)\times\{b\}:t=c,d,e,f\}
$$
deze gelijkheden vertalen zich in
$$
ua(k,n+1)=5\times ub(k-1,n)
$$
en
$$
ub(k,n+1)=4\times ub(k,n)+ ua(k,n).
$$
Met behulp van deze twee relaties kunnen formules voor $ua(k,n)$ en $ub(k,n)$ en dus ook voor $|U_{k,n}|$ afgeleid worden.

Voor $k=0$: $ua(0,n)=0$ (geen woord zonder $a$ eindigt in een $a$), en dus $ub(0,n+1)=4\times ub(0,n)$ en omdat $ub(0,1)=1$ zien we $ub(0,n)=4^{n-1}$.

Nu $k=1$: er geldt $ua(1,1)=1$, $ub(1,1)=0$ en $ub(1,2)=1$
(de verzamelingen zijn eenvoudig op te schrijven).
Dan volgt uit de eerste formule voor $n\ge 2$ dat
$$
ua(1,n)=5\times ub(0,{n-1})=5\times4^{n-2}.
$$
en uit de tweede:
$$
ub(1,n+1) = 4ub(1,n)+ua(1,n)
$$
en voor $n\ge2$ wordt dit
$$
ub(1,n+1) = 4ub(1,n)+5\times4^{n-2}
$$
Met de beginvoorwaarde $ub(1,2)=1$ geeft Maple's rsolve de oplossing
$$
ub(1,n) = \frac{5n-6}{64}\times4^n
$$
Nu volgt voor $n\ge2$:
$$
|U_{1,n}|=ua(1,n)+5\times ub(1,n) =
5\times 4^{n-2}+5\times\frac{5n-6}{64}\times 4^n = 25(n-2)4^{n-3}+10\times 4^n
$$
en $|U(1,1)|=1$.

Dit gaat zo verder, wel opletten dat bij het oplossen van latere recursie de juiste beginvoorwaarde wordt meegenomen.

kphart

Vragen naar aanleiding van dit antwoord? Klik rechts..!
maandag 2 juni 2014