Ez egy tanulságos Markov-láncos feladat, érdemes végigszámolni.
Legyen a húzások száma \(\displaystyle T \). Minden \(\displaystyle 0 \le t < T \) egészre nézzük meg, hogy \(\displaystyle t \) húzás után a legközelebbi húzásban hány cetli közül kell húzni, ez legyen \(\displaystyle X_t \), valamint legyen \(\displaystyle Y_t \) azon törpék száma, akik önmagukat húzzák ebben a húzásban. Tehát \(\displaystyle 0 \le t < T \) esetén \(\displaystyle 2 \le X_t \le 7 \). Terjesszük ki az \(\displaystyle X \) sorozatot úgy, hogy \(\displaystyle X_t = 0 \) ha \(\displaystyle T \le t \).
Nyilván \(\displaystyle X_0 = 7 \). A játék szabályai szerint ha \(\displaystyle 0 \le t < T \), akkor \(\displaystyle X_{t+1} = Y_t \), kivéve ha \(\displaystyle Y_t = 1 \), amely esetben \(\displaystyle X_{t+1} = 7 \). Mármost rögzített \(\displaystyle X_t \) mellett \(\displaystyle Y_t \) eloszlása nem függ az előzményektől. Az eloszlást pontosan meg is tudjuk adni: \(\displaystyle P(Y_t = y \mid X_t = x) = \textrm{A008290}(y, x)/x! \). Itt az A008290(y, x) szám x elem azon permutációinak a száma, amiben pontosan y fixpoint van, az OEIS A008290 sorozata szerint. Ez a valószínűség nulla, ha \(\displaystyle x < y \). Íme a feltételes eloszlások táblázata.
\(\displaystyle x =\) | 2 | 3 | 4 | 5 | 6 | 7 |
\(\displaystyle P(Y_t=0 \mid X_t=x) =\) | 1/2 | 2/6 | 9/24 | 44/120 | 265/720 | 1854/5040 |
\(\displaystyle P(Y_t=1 \mid X_t=x) =\) | 0 | 3/6 | 8/24 | 45/120 | 264/720 | 1855/5040 |
\(\displaystyle P(Y_t=2 \mid X_t=x) =\) | 1/2 | 0 | 6/24 | 20/120 | 135/720 | 924/5040 |
\(\displaystyle P(Y_t=3 \mid X_t=x) =\) | 0 | 1/6 | 0 | 10/120 | 40/720 | 315/5040 |
\(\displaystyle P(Y_t=4 \mid X_t=x) =\) | 0 | 0 | 1/24 | 0 | 15/720 | 70/5040 |
\(\displaystyle P(Y_t=5 \mid X_t=x) =\) | 0 | 0 | 0 | 1/120 | 0 | 21/5040 |
\(\displaystyle P(Y_t=6 \mid X_t=x) =\) | 0 | 0 | 0 | 0 | 1/720 | 0 |
\(\displaystyle P(Y_t=7 \mid X_t=x) =\) | 0 | 0 | 0 | 0 | 0 | 1/5040 |
A fentiekből az is következik, hogy ha rögzítjük \(\displaystyle x \)-et ahol \(\displaystyle 1 < x \), akkor az \(\displaystyle X_t = x \) feltétel mellett \(\displaystyle X_{t+1} \) eloszlása független az előzményektől, vagyis az \(\displaystyle X_0, \dots, X_{t-1} \) számoktól (és mellesleg még a húzott nevektől is), és ez a feltételes eloszlás bármely \(\displaystyle t \)-re ugyanaz. Ez azt jelenti, hogy \(\displaystyle X \) egy stacionáris markov lánc. Mivel \(\displaystyle X_{t+1} \) az \(\displaystyle Y_t \) fent leírt függvénye eloszlásból, és \(\displaystyle Y_t \) feltételes eloszlását az előbb kiszámoltuk, ezért \(\displaystyle X_{t+1} \) feltételes eloszlását (az átmenet valószínűségeket) is meg tudjuk adni.
\(\displaystyle x =\) | 2 | 3 | 4 | 5 | 6 | 7 |
\(\displaystyle P(X_{t+1}=0 \mid X_t=x) =\) | 1/2 | 2/6 | 9/24 | 44/120 | 265/720 | 1854/5040 |
\(\displaystyle P(X_{t+1}=2 \mid X_t=x) =\) | 1/2 | 0 | 6/24 | 20/120 | 135/720 | 924/5040 |
\(\displaystyle P(X_{t+1}=3 \mid X_t=x) =\) | 0 | 1/6 | 0 | 10/120 | 40/720 | 315/5040 |
\(\displaystyle P(X_{t+1}=4 \mid X_t=x) =\) | 0 | 0 | 1/24 | 0 | 15/720 | 70/5040 |
\(\displaystyle P(X_{t+1}=5 \mid X_t=x) =\) | 0 | 0 | 0 | 1/120 | 0 | 21/5040 |
\(\displaystyle P(X_{t+1}=6 \mid X_t=x) =\) | 0 | 0 | 0 | 0 | 1/720 | 0 |
\(\displaystyle P(X_{t+1}=7 \mid X_t=x) =\) | 0 | 3/6 | 8/24 | 45/120 | 264/720 | 1856/5040 |
Most akkor számoljuk ki \(\displaystyle T \) várható értékét. Erre stacionáris Markov-láncoknál a szokásos módszer a következő. Jelölje a maradék lépések számának, vagyis \(\displaystyle (T-t) \)-nek, a várható értékét \(\displaystyle a_x \) az \(\displaystyle X_t = x \) feltétel mellett. A fentiek miatt a maradék lépések számának feltételes eloszlása is független az előzményektől, és \(\displaystyle t \)-től is. Nyilván \(\displaystyle a_0 = 0 \). A többi (\(\displaystyle 2 \le x \le 7\)) esetre felírhatunk egy-egy lineáris egyenletet a fenti átmenet valószínűségek alapján.
\(\displaystyle a_x = 1 + \sum_k P(X_{t+1}=k \mid X_t=x) \cdot a_k \)
Az egyenletrendszer megoldása után, mivel \(\displaystyle X_0 = 7 \), ezért a húzások számának várható értéke \(\displaystyle a_7 \).
A konkrét esetben az egyenletrendszer a következő.
\(\displaystyle
(a_2, a_3, a_4, a_5, a_6, a_7) \cdot
\begin{pmatrix}
1/2-1 &0 &6/24 &20/120 &135/720 & 924/5040 \\
0 &1/6-1 &0 &10/120 & 40/720 & 315/5040 \\
0 &0 &1/24-1 & 0 & 15/720 & 70/5040 \\
0 &0 &0 & 1/120-1 & 0 & 21/5040 \\
0 &0 &0 & 0 & 1/720-1 & 0 \\
0 &3/6 &8/24 &45/120 &264/720 &1856/5040-1 \\
\end{pmatrix} =
\)
\(\displaystyle
= (-1, -1, -1, -1, -1, -1)
\)
Ennek a megoldása
\(\displaystyle
(a_2, a_3, a_4, a_5, a_6, a_7) = (9713740330, 13115308479, 11826442740, 12225059935, 12123252750, 12145107135) / 4856870165
\)
Így a sorsolások átlagos száma \(\displaystyle a_7 = 12145107135/4856870165 \), ami körülbelül 2.50.
|