Discrepanza tra teste e le code
-
16-10-2019 - |
Domanda
Si consideri una sequenza di $ n $ lanci di una moneta imparziale. Sia $ H_i $ denota il valore assoluto della eccedenza del numero di teste nel corso code visto nel primo $ i $ ribalta. Definire $ H = \ text {max} _I H_i $. Mostra che $ E [H_i] = \ Theta (\ sqrt {i}) $ e $ E [H] = \ Theta (\ sqrt {n}) $.
Questo problema appare nel primo capitolo del `algoritmi randomizzati da Raghavan e Motwani, quindi forse c'è una dimostrazione elementare della dichiarazione di cui sopra. Sono in grado di risolvere, in modo Gradirei qualsiasi aiuto.
Soluzione
Il tuo lanci della moneta formare un random walk unidimensionale $ x_0, X_1, \ ldots $ a partire da $ x_0 = 0 $, con $ X_ {i + 1} = x_i \ pm 1 $, ciascuna delle opzioni con probabilità $ 1/2 $. Ora $ H_i = | x_i | $ e così $ H_i ^ 2 = x_i ^ 2 $. E 'facile calcolare $ E [x_i ^ 2] = i $ (questa è solo la varianza), e così $ E [H_i] \ leq \ sqrt {E [H_i ^ 2]} = \ sqrt {i} $ da convessità. Sappiamo anche che $ x_i $ è distribuito più o meno normale con media zero e varianza $ i $, e così si può calcolare $ E [H_i] \ approx \ sqrt {(2 / \ pi) i} $.
leggePer quanto riguarda $ E [\ Max_ {i \ leq n} H_i] $, abbiamo la dei quali (forse) porta iterata logaritmo , ci aspettiamo qualcosa di leggermente più grande di $ \ sqrt {n} $. Se siete bravi con un limite superiore di $ \ tilde {O} (\ sqrt {n}) $, è possibile utilizzare una grande deviazione vincolato per ogni $ x_i $ e poi l'unione legata, però che ignora il fatto che il $ x_i $ sono correlati.
Edit: Come spesso accade, $ \ Pr [\ Max_ {i \ leq n} x_i = k] = \ Pr [X_n = k] + \ Pr [X_n = k + 1] $ a causa del principio di riflessione, vedi questa domanda . Così $$ \ 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} $$ dal momento che $ \ Pr [H_n = k] = \ Pr [X_n = k] + \ Pr [X_n = -k] = 2 \ Pr [X_n = k] $. Adesso $$ \ 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 quindi $ E [\ Max_ {i \ leq n} H_i] \ leq 2E [H_n] + \ Theta (1) = O (\ sqrt {n}) $. L'altra direzione è simile.
Altri suggerimenti
È possibile utilizzare la mezza distribuzione normale per dimostrare la risposta.
Gli stati di normale distribuzione che se $ X $ è una distribuzione normale con media 0 e varianza $ \ sigma ^ 2 $, quindi $ | X | $ segue un metà distribuzione con $ media \ sigma \ sqrt {\ frac {2} {\ pi}} $, e varianza $ \ sigma ^ 2 (1-2 / \ pi) $. Questo dà la risposta necessaria, dal momento che la varianza $ \ sigma ^ 2 $ del normale passeggiata è $ n $, e si può approssimare la distribuzione di $ X $ per una distribuzione normale utilizzando il teorema del limite centrale.
$ X $ è la somma del random walk come detto Yuval Filmus.
In primo $ 2i $ ribalta, supponiamo otteniamo $ k $ code, quindi $ H_ {} 2i = 2 | i-k | $. Perciò, \ Begin {align} E (H_ {2i}) & = 2 \ sum_ {k = 0} ^ {i} \ binom {2i} {k} (\ frac {1} {2}) ^ {2i} \ cdot 2 (IK) \ \ & = (\ 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 \ lasciato (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} Utilizzare di Stirling approssimazione , sappiamo $ E (H_ {} 2i) = \ Theta ( \ sqrt {} 2i) $.