Rozbieżność między głowami a ogonami

Rozważ sekwencję rzutów bezstronnej monety. Niech oznacza wartość bezwzględną nadwyżki liczby głów nad ogonami widzianej w pierwszych rzutach . Zdefiniuj . Pokaż, że i . $n$ $H_i$ $i$ $H=\text{max}_i H_i$ $E[H_i]=\Theta ( \sqrt{i} )$ $E[H]=\Theta( \sqrt{n} )$

Ten problem pojawia się w pierwszym rozdziale „Randomized algorytmów” Raghavan i Motwani, więc być może istnieje elementarny dowód na powyższe stwierdzenie. Nie jestem w stanie go rozwiązać, więc byłbym wdzięczny za wszelką pomoc.

probability-theory randomized-algorithms

— Plummer
źródło

Odpowiedzi:

Twoje rzuty monetą tworzą jednowymiarowy losowy spacer zaczynające się od , z , każda z opcji z prawdopodobieństwem . Terazi tak . Łatwo obliczyć (to tylko wariancja), a więc z wypukłości. Wiemy również, że jest rozłożony w przybliżeniu normalnie z zerową średnią i wariancją , więc możesz obliczyć . $X_0,X_1,\ldots$ $X_0 = 0$ $X_{i+1} = X_i \pm 1$ $1/2$ $H_i = |X_i|$ $H_i^2 = X_i^2$ $E[X_i^2] = i$ $E[H_i] \leq \sqrt{E[H_i^2]} = \sqrt{i}$ $X_i$ $i$ $E[H_i] \approx \sqrt{(2/\pi)i}$

Jeśli chodzi o , mamy prawo iterowanego logarytmu , co (być może) prowadzi nas do oczekiwania czegoś nieco większego niż . Jeśli jesteś dobry w górnej granicy , możesz użyć dużej granicy odchylenia dla każdego a następnie granicy unii, chociaż ignoruje to fakt, że są powiązane. $E[\max_{i \leq n} H_i]$ $\sqrt{n}$ $\tilde{O}(\sqrt{n})$ $X_i$ $X_i$

Edycja: Jak to się dzieje, ze względu na zasadę odbicia, patrz to pytanie . Więc od . Teraz a zatem $\Pr[\max_{i \leq n} X_i = k] = \Pr[X_n = k] + \Pr[X_n = k+1]$

\begin{aligned} E [max_{i \leq n} X_{i}] & = \sum_{k \geq 0} k (Pr [X_{n} = k] + Pr [X_{n} = k + 1]) \\ = \sum_{k \geq 1} (2 k - 1) Pr [X_{n} = k] \\ = \sum_{k \geq 1} 2 k Pr [X_{n} = k] - \frac{1}{2} + \frac{1}{2} Pr [X_{n} = 0] \\ = E [H_{n}] + Θ (1), \end{aligned}

$\begin{align*} E[\max_{i \leq n} X_i] &= \sum_{k \geq 0} k(\Pr[X_n = k] + \Pr[X_n = k+1]) \\ &= \sum_{k \geq 1} (2k-1) \Pr[X_n = k] \\ &= \sum_{k \geq 1} 2k \Pr[X_n = k] - \frac{1}{2} + \frac{1}{2}\Pr[X_n = 0] \\ &= E[H_n] + \Theta(1), \end{align*}$

Pr [H_{n} = k] = Pr [X_{n} = k] + Pr [X_{n} = - k] = 2 Pr [X_{n} = k]

$\Pr[H_n = k] = \Pr[X_n = k] + \Pr[X_n = -k] = 2\Pr[X_n = k]$

\frac{max_{ja \leq n} X_{ja} + max_{ja \leq n} (- X_{ja})}{2)} \leq max_{ja \leq n} {H.}_{ja} \leq max_{ja \leq n} X_{ja} + max_{ja \leq n} (- X_{ja}),

$\frac{\max_{i \leq n} X_i + \max_{i \leq n} (-X_i)}{2} \leq \max_{i \leq n} H_i \leq \max_{i \leq n} X_i + \max_{i \leq n} (-X_i),$

E [max_{i \leq n} H_{i}] \leq 2 E [H_{n}] + Θ (1) = O (\sqrt{n})

$E[\max_{i \leq n} H_i] \leq 2E[H_n] + \Theta(1) = O(\sqrt{n})$ . Drugi kierunek jest podobny.

— Yuval Filmus
źródło

Po udowodnieniu, że , nie możemy powiedzieć, że dla mamy drugi wynik, tzn. Brak jest większy niż .

E [H_{i}] = Θ (\sqrt{i})

$E[H_{i}] = \Theta ( \sqrt{i} )$

i = n

$i=n$

E [H_{i}]

$E[H_{i}]$

Θ (\sqrt{n})

$\Theta ( \sqrt{n} )$

— chazisop,

Jeśli były niezależne, wówczas wniosek nie byłby prawdziwy, ponieważ w rzeczywistości oczekujesz, że niektóre z tych wartości będą nieco większe niż oczekiwane. Na ogół nie jest prawdą, że .

H_{i}

$H_i$

E [max (A, B)] = max (E [A], E [B])

$E[\max(A,B)] = \max(E[A],E[B])$

— Yuval Filmus

Prawo iterowanego logarytmu nie ma tutaj zastosowania, ponieważ jest ustalone i nie normalizujemy się przez . Odpowiedź na to .

n

$n$

i

$i$

E max_{i \leq n} H_{i}

$\mathrm{E} \max_{i\leq n} H_i$

θ (\sqrt{n})

$\theta(\sqrt{n})$

— Peter Shor,

+1 za pierwszą część. ale szczerze mówiąc, nie rozumiem drugiej części (czy możesz opracować więcej informacji). Nie oznacza to jednak, że jest to nieprawidłowe.

— AJed

Niezły dowód. Ale utknąłem, jak udowodnić, że jest dolną granicą ? Wygląda na to, że w odpowiedzi nie wspomniano żadnych szczegółów na temat dolnej granicy.

\sqrt{n}

$\sqrt{n}$

E (H_{i})

$E(H_i)$

— konjac

Możesz użyć rozkładu półnormalnego, aby potwierdzić odpowiedź.

Rozkład półnormalny stwierdza, że jeśli jest rozkładem normalnym ze średnią 0 i wariancją , tonastępuje połowa rozkładu ze średnią i wariancją . Daje to wymaganą odpowiedź, ponieważ wariancja normalnego marszu wynosi , i można przybliżać rozkład do rozkładu normalnego za pomocą centralnego twierdzenia granicznego. $X$ $\sigma^2$ $|X|$ $\sigma \sqrt{\frac{2}{\pi}}$ $\sigma^2 (1-2/\pi)$ $\sigma^2$ $n$ $X$

$X$ jest sumą losowego marszu, jak wspomniał Yuval Filmus.

— AJed
źródło

Nie wolę tego, co opublikowałem. chociaż daje dolną granicę, nic nie można powiedzieć o górnej granicy. Próbowałem użyć argumentu maksymalnej dystrybucji, aby go rozwiązać, okazało się to brzydką integracją. Ale dobrze jest znać wszystkie te rozkłady.

— AJed

W pierwszych załóżmy, że otrzymujemy ogonów, a następnie. Dlatego Użyj przybliżenia Stirlinga , wiemy . $2i$ $k$ $H_{2i}=2|i-k|$

\begin{aligned} mi ({H.}_{2) ja}) & = 2) \sum_{k = 0}^{ja} (\binom{2) ja}{k}) (\frac{1}{2)})^{2) ja} \cdot 2) (ja - k) \\ = (\frac{1}{2)})^{2) ja - 2)} [ja \sum_{k = 0}^{ja} (\binom{2) ja}{k}) - \sum_{k = 0}^{ja} k (\binom{2) ja}{k})] \\ = (\frac{1}{2)})^{2) ja - 2)} [ja ({2)}^{2) ja} + (\binom{2) ja}{ja})) / 2) - 2) ja \sum_{k = 0}^{ja - 1} (\binom{2) ja - 1}{k})] \\ = (\frac{1}{2)})^{2) ja - 2)} \cdot ja [{2)}^{2) ja - 1} + (\binom{2) ja}{ja}) / 2) - 2) \cdot {2)}^{2) ja - 1} / 2)] \\ = 2) ja \cdot (\binom{2) ja}{ja}) / {2)}^{2) ja} . \end{aligned}

$\begin{align} E(H_{2i}) & =2\sum_{k=0}^{i}\binom{2i}{k}(\frac{1}{2})^{2i}\cdot 2(i-k)\\ & = (\frac{1}{2})^{2i-2}\left[i\sum_{k=0}^{i}\binom{2i}{k}-\sum_{k=0}^ik\binom{2i}{k}\right]\\ & = (\frac{1}{2})^{2i-2}\left[i\left(2^{2i}+\binom{2i}{i}\right)/2-2i\sum_{k=0}^{i-1}\binom{2i-1}{k}\right]\\ & = (\frac{1}{2})^{2i-2}\cdot i\left[2^{2i-1}+\binom{2i}{i}/2-2\cdot 2^{2i-1}/2\right]\\ & = 2i\cdot\binom{2i}{i}/2^{2i}. \end{align}$

E (H_{2 i}) = Θ (\sqrt{2 i})

$E(H_{2i})=\Theta(\sqrt{2i})$

— wodny
źródło

nie powinniśmy brać pod uwagę przypadków, w których ? wygląda na to, że brakuje Ci mnożenia 2, prawda?

i < k \leq 2 i

$i<k\leq 2i$

— omerbp