Discrepanza tra teste e le code

Question

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.

Answer 1

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} $.

legge

Per 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.

Answer 2

È 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.

Answer 3

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) $.