Discrepância entre cara e coroa

12

Considere uma sequência de n lançamentos de uma moeda imparcial. Deixe HEu denotar o valor absoluto do excesso do número de cabeças sobre caudas vistas nos primeiros Eu flips. Defina H=maxEuHEu . Mostre que E[HEu]=Θ(Eu)eE[H]=Θ(n).

Esse problema aparece no primeiro capítulo de `Algoritmos aleatórios 'de Raghavan e Motwani, portanto, talvez haja uma prova elementar da afirmação acima. Não consigo resolvê-lo, por isso gostaria de receber qualquer ajuda.

Plummer
fonte

Respostas:

9

Seu coin flips formar uma caminhada unidimensional aleatória a partir de X 0 = 0 , com X i + 1 = X i ± 1 , cada uma das opções com probabilidade 1 / 2 . Agora H i = | X i | e então H 2 i = X 2 i . É fácil calcular E [ X 2 i ] =X0 0,X1,...X0 0=0 0XEu+1=XEu±11/2HEu=|XEu|HEu2=XEu2 (esta é apenas a variação), e então E [ H i ] E[XEu2]=Eu de convexidade. Sabemos também queXié distribuído aproximadamente normal com média zero e variânciai, e assim você pode calcularE[Hi]E[HEu]E[HEu2]=EuXEui .E[Hi](2/π)i

Quanto a , temos a lei do logaritmo iterado , que (talvez) nos leva a esperar algo um pouco maior que E[maxinHi] . Se você é bom com um limite superior de ˜ O (n, você pode usar um grande desvio com destino a cadaXie depois a união obrigado, no entanto, que ignora o fato de que oXiestão relacionados.O~(n)XiXi

Edit: Por acaso, devido ao princípio de reflexão, consulte esta pergunta . Então E [ max i n X i ]Pr[maxinXi=k]=Pr[Xn=k]+Pr[Xn=k+1] uma vez quePr[Hn=k]=Pr[Xn=k]+Pr[Xn=-k]=2Pr[Xn=k]. Agora max i n X i + max i n (-

E[maxinXi]=k0k(Pr[Xn=k]+Pr[Xn=k+1])=k1(2k1)Pr[Xn=k]=k12kPr[Xn=k]12+12Pr[Xn=0]=E[Hn]+Θ(1),
Pr[Hn=k]=Pr[Xn=k]+Pr[Xn=k]=2Pr[Xn=k] e,portanto,E[maxinHi]2E[Hn]+Θ(1)=O(
maxinXi+maxin(Xi)2maxinHimaxinXi+maxin(Xi),
. A outra direção é semelhante.E[maxinHi]2E[Hn]+Θ(1)=O(n)
Yuval Filmus
fonte
E[Hi]=Θ(i) , couldn't we say that for i=n we have the second result, i.e. no E[Hi] is greater than Θ(n).
chazisop
1
If the Hi were independent, then the conclusion won't be true, since you actually expect some of these values to be somewhat larger than the expectation. It's not true in general that E[max(A,B)]=max(E[A],E[B]).
Yuval Filmus
1
The law of the iterated logarithm doesn't apply here, since n is fixed and we're not normalizing by i. The answer for EmaxinHi is θ(n).
Peter Shor
+1 for the first part. but I honestly dont understand the second part (can you elaborate more plz). This does not mean that it is not correct though.
AJed
1
Nice proof. But I am stuck at how to prove n is the lower bound of E(Hi)? It seems that the answer mentions no details about the lower bound.
konjac
2

You can use the half-normal distribution to prove the answer.

The half-normal distribution states that if X is a normal distribution with mean 0 and variance σ2, then |X| follows a half distribution with mean σ2π, and variance σ2(12/π). This gives the required answer, since the variance σ2 of the normal walk is n, and you can approximate the distribution of X to a normal distribution using the central limit theorem.

X is the sum of the random walk as Yuval Filmus mentioned.

AJed
fonte
I dont prefer this that I posted.. . although it gives the lower bound, nothing can be told about the upper bound. I tried to use a maximum distribution argument to solve it, it turned out to be an ugly integration. But it is good to know all these distributions.
AJed
2

In first 2i flips, suppose we get k tails, then H2i=2|ik|. Therefore,

E(H2i)=2k=0i(2ik)(12)2i2(ik)=(12)2i2[ik=0i(2ik)k=0ik(2ik)]=(12)2i2[i(22i+(2ii))/22ik=0i1(2i1k)]=(12)2i2i[22i1+(2ii)/2222i1/2]=2i(2ii)/22i.
Use Stirling's approximation, we know E(H2i)=Θ(2i).
Aqua
fonte
shouldn't we take into account cases where i<k2i? it seems that you miss a multiplication factor of 2, right?
omerbp