Gra z kartkami w urnie

[nvc23]

W urnie jest 100 kartek ponumerowanych od 1 do 100. Wyciągasz kolejno kartki tak długo, aż natrafisz na kartkę z numerem mniejszym niż którykolwiek wyciągnięty wcześniej. Za każde ciągnienie (z wyjątkiem ostatniego) dostajesz złotówkę. Czy gra jest korzystna dla gracza, jeśli za przystąpienie płaci się 3 zł?

[M Maciejewski]

Podpowiem.
Niech \(\displaystyle{ X_1,X_2,X_3,\ldots}\) oznaczają zmienne losowe, przyjmujące jako wartość wylosowaną liczbę w pierwszym, drugim, itd, rzucie.
Niech \(\displaystyle{ X}\) oznacza zmienną losową, przyjmującą jako wartość liczbę wygranych złotówek (a więc liczbę wyciągniętych liczb poza ostatnią.

Teraz proste, ale ważne spostrzeżenie:
jeśli możemy losować np. 5 razy, to oznacza, że druga liczba jest większa od pierwszej, trzecia liczba jest większa od drugiej lub pierwszej, a więc większa od pierwszej, czwarta liczba jest większa od trzeciej, drugiej lub pierwszej, a więc od pierwszej, i piąta liczba musi być większa od pierwszej. Czyli pierwsza liczba musi być cały czas najmniejsza.

Stąd:
\(\displaystyle{ \PP(X=1)=\PP(X_2<X_1)}\) (druga liczba jest mniejsza od pierwszej, więc kończymy i wygrywamy 1zł.
\(\displaystyle{ \PP(X\geq 2)=\PP(X_2>X_1)}\).
\(\displaystyle{ \PP(X\geq 3)=\PP(X_2,X_3>X_1)}\)
\(\displaystyle{ \PP(X\geq 4)=\PP(X_2,X_3,X_4>X_1)}\)
i tak dalej.

Następnie:
\(\displaystyle{ \PP(X=k)=\PP(X\geq k,X\not\geq k+1)=\PP(X_2,X_3,\ldots,X_k>X_1,\ X_{k+1}<X_1)}\).

Następnie liczymy wartość oczekiwaną zmiennej \(\displaystyle{ X}\):
\(\displaystyle{ \EE(X)=\sum_{k=1}^\infty k\cdot \PP(X=k)}\). Jeśli \(\displaystyle{ \EE(X)>3}\), to gra się opłaca.-- 25 cze 2016, o 22:33 --W sumie lepiej skorzystać ze wzoru \(\displaystyle{ \EE(X)=\sum_{k=1}^\infty \PP(X\geq k)}\) .

[kinia7]

Teraz proste, ale ważne spostrzeżenie:
jeśli możemy losować np. 5 razy, to oznacza, że druga liczba jest większa od pierwszej, trzecia liczba jest większa od drugiej \(\displaystyle{ lub}\) pierwszej, a więc większa od pierwszej, czwarta liczba jest większa od trzeciej, drugiej \(\displaystyle{ lub}\) pierwszej, a więc od pierwszej, i piąta liczba musi być większa od pierwszej. Czyli pierwsza liczba musi być cały czas najmniejsza.

zamiast \(\displaystyle{ lub}\) musi być \(\displaystyle{ i}\)

Następnie liczymy wartość oczekiwaną zmiennej \(\displaystyle{ X}\):
\(\displaystyle{ \EE(X)=\sum_{k=1}^\infty k\cdot \PP(X=k)}\). Jeśli \(\displaystyle{ \EE(X)>3}\), to gra się opłaca.

-- 25 cze 2016, o 22:33 --

W sumie lepiej skorzystać ze wzoru \(\displaystyle{ \EE(X)=\sum_{k=1}^\infty \PP(X\geq k)}\) .

To ile wynosi \(\displaystyle{ \EE(X)}\)?

[M Maciejewski]

zamiast \(\displaystyle{ lub}\) musi być \(\displaystyle{ i}\)

Wydaje mi się, że jednak powinno być lub, ponieważ gra się kończy dopiero wtedy, gdy wylosowaliśmy liczbę mniejszą od wszystkich pozostałych, a więc gramy dalej, gdy wylosowaliśmy liczbę, która jest większa od przynajmniej jednej poprzedniej liczby. Sprowadza się to do tego, że wylosowana liczba musi być większa od pierwszej liczby.

[Santiago A]

To ile wynosi \(\displaystyle{ \EE(X)}\)?

Zwartego wzoru nie podam, ale odwołam się do OEIS, gdzie istnieje już stosowny ciąg. Przyjmijmy, że karteczek nie jest \(\displaystyle{ 100}\), tylko \(\displaystyle{ n}\), natomiast szukana wartość oczekiwana to \(\displaystyle{ a(n) / n!}\). Jeżeli nie pomyliłem się w rachunkach, to wykładniczą funkcją tworzącą dla \(\displaystyle{ a(n)}\) jest

\(\displaystyle{ \frac{1 - x \log (1-x) }{1-x}}\).

Można jednak podać półzwarty wzór, skąd pierwsza lepsza mądra głowa wyciągnie interpretację kombinatoryczną:

\(\displaystyle{ \frac{a(n)}{n!} =1 + \sum_{k=1}^{n-1} \frac 1 k}\).

Ewentualnie bez tej jedynki, nie mam już siły na wgryzanie się w zawiłą treść zadania.

[kinia7]

To odpowie ktoś na pytanie autora: "Czy gra jest korzystna dla gracza?"

-- 27 cze 2016, o 19:26 --

'

Teraz proste, ale ważne spostrzeżenie:
jeśli możemy losować np. 5 razy, to oznacza, że druga liczba jest większa od pierwszej, trzecia liczba jest większa od drugiej lub pierwszej

Z tego zapisu wynika, że gracz dostanie trzecią złotówkę gdy trzecia liczba będzie mniejsza od drugiej ale większa od pierwszej.

Wyciągasz kolejno kartki tak długo, aż natrafisz na kartkę z numerem mniejszym niż którykolwiek wyciągnięty wcześniej.

Czyli trzeci wylosowany numer musi być większy i od pierwszego i od drugiego.
W przeciwnym razie zabawa się kończy na otrzymaniu dwóch złotych. Złotówka w plecy

-- 28 cze 2016, o 16:12 --

Mnie się wydaje, że gra nie jest opłacalna, gdyż \(\displaystyle{ \EE(n)<2}\)zł.

-- 28 cze 2016, o 19:35 --

\(\displaystyle{ \EE(n)=\sum_{n=1}^{\infty}n\cdot P_n \approx 1 \cdot \frac{1}{2} +2 \cdot \frac{1}{3} +3 \cdot \frac{1}{8} +4 \cdot \frac{1}{30} +5 \cdot \frac{1}{144} +6 \cdot \frac{1}{840} +7 \cdot \frac{1}{5760} \approx 1,72}\) zł

[kinia7]

\(\displaystyle{ k}\) - ilość kartek w urnie
\(\displaystyle{ n}\) - ilość otrzymanych złotówek w jednej grze, \(\displaystyle{ n\in\{1,2,...,k\}}\)
\(\displaystyle{ P^k_n}\) - prawdopodobieństwo otrzymania dokładnie \(\displaystyle{ n}\) złotówek, gdy w urnie jest \(\displaystyle{ k}\) kartek

\(\displaystyle{ P_n^k=\left\{\ \begin{array}{lcrcccl} \frac{n}{(n+1)!} & \ dla\ & 0 &< & n & < & k\\\ \\ \ \ \frac{1}{n!} & \ dla\ & 0 & < & n & = & k\end{array}}\)

\(\displaystyle{ \EE(n)=\sum_{n=1}^kn\cdot P^k_n=\frac{1}{(k-1)!}+\sum_{n=1}^{k-1}\frac{n^2}{(n+1)!}\qquad\qquad\qquad \begin{cases}k=2\ \rightarrow \ \EE(n) =1,5\\k=3\ \rightarrow \ \EE(n) \approx 1,66667\\k=5\ \rightarrow \ \EE(n) \approx1,71667\\ k=7\ \rightarrow \ \EE(n) \approx 1,71825 \\ k=10\ \rightarrow \ \EE(n) \approx 1,71828 \\ k=100\ \rightarrow \ \EE(n) \approx 1,71828 \\ k \rightarrow \infty\ \rightarrow \ \EE(n) =e-1\end{cases}}\)