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