Écart entre les têtes et les queues

12

Considérons une séquence de n flips d'une pièce non biaisée. Soit Hi la valeur absolue de l'excédent du nombre de têtes sur les queues vu dans les premiers i flips. Définissez H=maxiHi . Montrer que E[Hi]=Θ(i)etE[H]=Θ(n).

Ce problème apparaît dans le premier chapitre des «algorithmes randomisés» de Raghavan et Motwani, il existe donc peut-être une preuve élémentaire de la déclaration ci-dessus. Je ne peux pas le résoudre, j'apprécierais donc toute aide.

Plummer
la source

Réponses:

9

Votre pièce flips forment une unidimensionnelle marche aléatoire X0,X1, à partir de X0=0 , avec Xi+1=Xi±1 , chacune des options avec une probabilité 1/2 . Maintenant Hi=|Xi|et donc Hi2=Xi2 . Il est facile de calculer E[Xi2]=i (c'est juste la variance), et doncE[Hi]E[Hi2]=i de la convexité. Nous savons également queXiest distribué à peu près normal avec une moyenne et une variancenullesi, et vous pouvez donc calculerE[Hi](2/π)i .

E[maxinHi]nO~(n)XiXi

Edit: En l' , raison du principe de réflexion, voir cette question . Donc puisque . Maintenant et doncPr[maxinXi=k]=Pr[Xn=k]+Pr[Xn=k+1]

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]
maxinXi+maxin(Xi)2maxinHimaxinXi+maxin(Xi),
E[maxinHi]2E[Hn]+Θ(1)=O(n). L'autre direction est similaire.
Yuval Filmus
la source
Après avoir prouvé que , ne pourrait-on pas dire que pour nous avons le deuxième résultat, c'est-à-dire qu'aucun n'est supérieur que . E[Hi]=Θ(i)i=nE[Hi]Θ(n)
chazisop
1
Si les étaient indépendants, la conclusion ne sera pas vraie, car vous vous attendez en fait à ce que certaines de ces valeurs soient un peu plus grandes que les attentes. Ce n'est pas vrai en général que . HiE[max(A,B)]=max(E[A],E[B])
Yuval Filmus
1
La loi du logarithme itéré ne s'applique pas ici, car est fixe et nous ne normalisons pas par . La réponse pour est . niEmaxinHiθ(n)
Peter Shor,
+1 pour la première partie. mais honnêtement, je ne comprends pas la deuxième partie (pouvez-vous élaborer plus plz). Cela ne signifie pas pour autant que ce n'est pas correct.
AJed
1
Belle preuve. Mais je ne sais pas comment prouver que est la borne inférieure de ? Il semble que la réponse ne mentionne aucun détail sur la borne inférieure. nE(Hi)
konjac
2

Vous pouvez utiliser la distribution semi-normale pour prouver la réponse.

La distribution semi-normale indique que si est une distribution normale avec une moyenne de 0 et une variance , alorssuit une demi-distribution avec la moyenne , et la variance . Cela donne la réponse requise, puisque la variance de la marche normale est , et vous pouvez approximer la distribution de à une distribution normale en utilisant le théorème de la limite centrale.Xσ2|X|σ2πσ2(12/π)σ2nX

X est la somme de la marche aléatoire comme l'a mentionné Yuval Filmus.

AJed
la source
Je ne préfère pas ce que j'ai publié ... bien qu'il donne la borne inférieure, on ne peut rien dire sur la borne supérieure. J'ai essayé d'utiliser un argument de distribution maximale pour le résoudre, il s'est avéré être une intégration moche. Mais il est bon de connaître toutes ces distributions.
AJed
2

Dans les premiers flips, supposons que nous obtenions queues, puis. Par conséquent, Utilisez l'approximation de Stirling , nous connaissons .2ikH2i=2|ik|

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.
E(H2i)=Θ(2i)
Aqua
la source
ne devrions-nous pas prendre en compte les cas où ? il semble que vous manquez un facteur de multiplication de 2, non? i<k2i
omerbp