Prawdopodobieństwo wystąpienia cyklu

[kristoffwp]

Mamy następujący problem:
W pudełkach ponumerowanych od 1 do 200 znajdują się kartki z numerami od 1 do 200 rozmieszczone w sposób losowy. Sto osób zostało ponumerowanych liczbami od 1 do 100. Osoba z numerem 1 otwiera pudełko z numerem 1, wyciąga kartkę i następnie otwiera pudełko z odczytanym numerem. Z kolejnymi pudełkami postępuje tak samo, do momentu gdy wróci do pudełka numer jeden. Każda z kolejnych osób postępuje analogicznie, z tym, że osoba z numerem \(\displaystyle{ k}\) zaczyna od pudełka z numerem \(\displaystyle{ k}\) i kończy swój cykl na nim. Jakie jest prawdopodobieństwo, że wszystkie 100 osób wróci do swojego pudełka po co najwyżej stu "ruchach". Podobno wyniesie ono ponad \(\displaystyle{ \frac{1}{4}}\). Jak się za to zabrać?

[Adifek]

Rozmieszczenie kartek dla każdej osoby jest takie samo, czy może być inne dla każdej z nich?

[kristoffwp]

Jest identyczne dla każdego.

[kristoffwp]

Nieśmiało się przypomnę ze swoim zapytaniem....

[Qń]

Oczywiście \(\displaystyle{ |\Omega |=200!}\).

Zauważmy, że zdarzenie przeciwne \(\displaystyle{ A'}\) polega na tym, że w permutacji naszego zbioru \(\displaystyle{ 200}\)-elementowego pojawi się cykl długości \(\displaystyle{ k\ge 101}\). Permutacji w których pojawi się cykl takiej długości jest:
\(\displaystyle{ \binom{200}{k}\cdot (k-1)! \cdot (200-k)! = \frac{200!}{k}}\)
(kolejno: wybieramy \(\displaystyle{ k}\) elementów do cyklu, traktując dowolny element jako początek cyklu ustalamy kolejność następnych \(\displaystyle{ k-1}\) elementów cyklu, permutujemy pozostałe \(\displaystyle{ 200-k}\) elementów)

W takim razie:
\(\displaystyle{ P(A') = \frac{\sum_{k=101}^{200}\frac{200!}{k}}{200!} = \sum_{k=101}^{200}\frac{1}{k} \approx \ln 200 - \ln 100 = \ln 2}\)
a zatem:
\(\displaystyle{ P(A)=1- \ln 2 \approx 0,31}\)

Q.

[kristoffwp]

Dziękuję za pomoc. Wiedziałem, że trzeba liczyć prawdopodobieństwo zdarzenia przeciwnego, ale nie wpadłem na to, jak się zabrać za ten 101+ elementowy cykl.