Komentarz

XXXI - II - Zadanie 5

Wypisujemy kolejno wyrazy ciągu $ (n_1, n_2, \ldots, n_k) $, gdzie $ n_1 = 1000 $, zaś $ n_j $ dla $ j > 1 $ jest liczbą całkowitą wybraną losowo z przedziału $ [0, n_{j-1} - 1] $ (wybór każdej liczby z tego przedziału jest jednakowo prawdopodobny). Kończymy wypisywanie, gdy wybrana liczba jest zerem, tzn. $ n_{k-1} $, $ n_k = 0 $, Długość $ k $ ciągu $ (n_1, n_2, \ldots, n_k) $ jest zmienną losową. Udowodnić, że wartość oczekiwana tej zmiennej losowej jest większa od 7.

Rozwiązanie

Dla danej liczby całkowitej nieujemnej $ n $ rozważmy zmienną losową $ X_n $ będącą długością $ k $ ciągu ($ n_1, n_2, \ldots, n_k $), gdzie $ n_1 = n $, $ n_j $ dla $ j > 1 $ jest liczbą całkowitą wybraną losowo z przedziału $ [0, n_{j-1} - 1] $, $ n_k = 0 $. Oznaczmy przez $ E_n $ wartość oczekiwaną tej zmiennej losowej. Oczywiście $ E_0 = 1 $, gdyż dla $ n = 0 $ istnieje tylko jeden ciąg mający długość $ 1 $, którego jedynym wyrazem jest $ 0 $. Niech $ n $ będzie liczbą naturalną. Przypuśćmy, że wyznaczyliśmy wartości oczekiwane $ E_m $ dla wszystkich $ m < n $. Rozważamy ciągi $ (n_1, n_2, \ldots, n_k) $, w których $ n_1 = n $. Możliwe są dwa następujące zdarzenia.

1) Albo $ n_2 = n - 1 $ (prawdopodobieństwo tego zdarzenia wynosi $ \frac{1}{n} $)
i wtedy wartość oczekiwana długości ciągu ($ n_2, \ldots, n_k $) wynosi $ E_{n-1} $, więc wartość oczekiwana długości ciągu ($ n_1, n_2, \ldots, n_k $) wynosi w tym przypadku $ E_{n-1} + 1 $,

2) albo $ n_2 < n - 1 $ (prawdopodobieństwo tego zdarzenia wynosi $ \frac{n-1}{n} $) i wtedy wartość oczekiwana długości ciągu $ (n_1, n_2, \ldots, n_k) $ jest dokładnie taka, jak wartość oczekiwana długości ciągu $ (m_1, m_2, \ldots, m_k) $, w którym $ m_1 = n - 1 $; ta wartość wynosi $ E_{n-1} $.

Wobec tego

\[<br /> E_n = \frac{1}{n} \left( E_{n-1} + 1 \right) + \frac{n-1}{n} E_{n-1} = E_{n-1} + \frac{1}{n}.<br /> \]

Ponieważ $ E_0 = 1 $, więc $ E_1 = 1 + \frac{1}{1} = 2, E_2 = 2 + \frac{1}{2}, \ldots, E_n = 2 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{n} $.

Interesująca nas w zadaniu wartość oczekiwana wynosi

\[<br /> \begin{split}<br /> E_{1000} & = 2 +<br /> \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{1000} =<br /> 2 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \left(\frac{1}{5} + \ldots + \frac{1}{8}\right)+ \\<br /> &\quad+\left(\frac{1}{9} + \ldots + \frac{1}{16}\right) +\left(\frac{1}{17} + \ldots + \frac{1}{32}\right) + \left(\frac{1}{33} + \ldots + \frac{1}{64}\right) +\\<br /> &\quad + \left(\frac{1}{65} + \ldots + \frac{1}{128}\right) + \left(\frac{1}{129} + \ldots + \frac{1}{256}\right) + \left(\frac{1}{257} + \ldots + \frac{1}{512}\right) +\\<br /> &\quad+\left(\frac{1}{513} + \ldots + \frac{1}{1024}\right) - \left(\frac{1}{1001} + \frac{1}{1002} + \ldots + \frac{1}{1024}\right).<br /> \end{split}<br /> \]

Liczba w ostatnim nawiasie jest mniejsza od $ \frac{24}{1000} $ natomiast każda
z liczb w poprzednich nawiasach (których jest osiem) jest większa od $ \frac{1}{2} $ gdyż w $ k $-tym nawiasie jest liczba

\[<br /> \frac{1}{2^k+1} + \frac{1}{2^k+2} + \ldots + \frac{1}{2^{k+1}}<br /> \]

będąca sumą $ 2^k $ składników, z których wszystkie są mniejsze (tylko ostatni równy). Wobec tego

\[<br /> \begin{split}<br /> E_{1000} &> 2 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + 8 \cdot \frac{1}{2} - \frac{24}{1000} = 6 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} - \frac{24}{1000} = \\<br /> &= 6 + \frac{1500 + 1000 + 750 - 72}{3000} = 6 + \frac{3178}{3000} > 7<br /> \end{split}<br /> \]

Uwaga. Przybliżona wartość liczby $ E_{1000} $ wynosi $ 8,48547 $.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz