Seria 11. Martyngały

1. (Model Polya) Urna zawiera b kul bialych i c czarnych. Losujemy kulę i zwracając dokladamy m kul tego samego koloru. Niech b_{n}, c_{n} oznaczają liczbe białych kul i liczbe czarnych. Niech X_{n} zoancza fakcję kul czarnych \frac{c_{n}}{b_{n}+c_{n}}, natomiast Y_{n} = 1 jesli w n-tym losowaniu wyciagnięto czarną kulę, 0 jeśli białą (dodatkowo Y_{0} = 1). Pokaż, że (X_{n}) jest martyngalem względem filtracji F_{n} = σ(Y_{0}, ..., Y_{n}). Wykaż, że X_{n} jest zbieżny do zmiennej granicznej X oraz udowodnij, że EX = \frac{c}{b+c}.

2. (Zadanie o Studencie) Student zna odpowiedź na m spośród n pytań, m < n. Jaką optymalną (ze względu na szansę wylosowania pytania na które zna odpowiedź) strategię wejścia do pokoju w którym profesor kolejno egzaminuje n studentów powinien przyjąć?

3. (Problem n-sekretarek) Mamy n uroczych dziewczyn spośród których chcemy wybrać najlepsżą możliwą. Możemy jedynie poznać relatywny porządek wchodzących kolejno kandydatek, to zanczy w momencie gdy k-ta dziweczyna wchodzi do pokoju znamy jej rangę. W momencie gdy kandyatka jest w pokoju musimy podjąć decyzję czy przyjmujemy ją do pracy czy nie. Nie możemy wracać do już odrzuconych dziewczyn. Znajdź strategię maksymalizującą sznsę wyboru najlepszej kandydatki. Mamy zatem zmienne X_{1}, ..., X_{n} oznaczające losową permutację. Jedyne co możemy obserwować to zmienne Y_{1}, ..., Y_{n} oznaczające relatywną pozycję kolejnych dziewczyn. Chcemy znaleźć strategie τ mierzalne wg filtracji zadanej przez F_{k} = σ(Y_{1}, ..., Y_{k}), które maksymalizują

E1_{X_{τ}} = n) = P(X_{τ} = n).

Zauważmy, że

E1_{X_{k}=n} = E(\frac{k}{n})1_{Y_{k}=k},

a więc de facto maksymalizujemy E\frac{τ}{n}1_{Y_{τ} =τ}.