Takie zadanko:
W poniższym algorytmie SEQUENCE przyjmujemy, że dana wejściowa\(\displaystyle{ M qslant 2}\).
Na wyjściu otrzymujemy nierosnący ciąg (\(\displaystyle{ n_{1}}\),...,\(\displaystyle{ n_{t}}\)) w którym \(\displaystyle{ n_{1} qslant n_{2} qslant ... n_{t}}\)
Dla j = 2,...M, niech zmienna losowa \(\displaystyle{ X_{j}}\)oznacza liczbę wystąpień j w wynikowym ciągu. Po wnikliwej analizie można dojść do wniosku, że dla wszystkich j = 2,...,M i całkowitego \(\displaystyle{ k qslant 0}\) zachodzi:
Pr[\(\displaystyle{ X_{j} = k] = j^{-k} (1 - frac{1}{j})}\)
Niech T będzie zmienną losową przyjmującą wartość t, gdy wynikowym ciągiem jest ( \(\displaystyle{ n_{1}}\),...,\(\displaystyle{ n_{t}}\)). Łatwo zauważyć, że wartość tej zmiennej określa czas działania algorytmu. Korzystając ze zdefiniowanej powyżej zmiennej losowej \(\displaystyle{ X_{j}}\) możemy zapisać \(\displaystyle{ T = 1+ \sum_{j=2}^{M} X _{j}}\)
a) Pokaż, że E[\(\displaystyle{ X_{j}}\)] = \(\displaystyle{ \frac{1}{j-1}}\)
b) Pokaż, że E[T] = O(log M)
A tu treść algorytmu SEQUENCE (nie wiem czy potrzebna czy nie ale nie zaszkodzi napisać)
SEQUENCE(M)
1. \(\displaystyle{ n_{0} M}\)
2. \(\displaystyle{ i 0}\)
3. repeat
4. \(\displaystyle{ i i+1}\)
5. \(\displaystyle{ n_{0} liczba wylosowana ze zbioru {1,...,n_{i-1}}}\)
6. until \(\displaystyle{ n_{i} = 1}\)
7. \(\displaystyle{ t i}\)
8. return (\(\displaystyle{ n_{1},...,n_{t}}\))