Nombre prévu de lancers de pièces pour obtenir N consécutifs, étant donné M consécutifs

Interviewstreet a eu son deuxième CodeSprint en janvier qui comprenait la question ci-dessous. La réponse programmatique est publiée mais ne comprend pas d'explication statistique.

(Vous pouvez voir le problème d'origine et la solution publiée en vous connectant au site Interviewstreet avec Google Creds, puis en accédant au problème Coin Tosses à partir de cette page .)

Lancer de pièces

Vous avez une pièce impartiale que vous souhaitez continuer à lancer jusqu'à ce que vous obteniez N têtes consécutives. Vous avez lancé la pièce M fois et, étonnamment, tous les lancers ont donné lieu à des têtes.

Quel est le nombre attendu de lancers supplémentaires nécessaires jusqu'à ce que vous obteniez N têtes consécutives?

Contribution:
La première ligne contient le nombre de cas T. Chacune des T lignes suivantes contient deux nombres N et M.

Production:
sortie T lignes contenant la réponse pour le cas de test correspondant. Imprimez la réponse arrondie à exactement 2 décimales.

Exemple d'entrée:
4
2 0
2 1
3 3
3 2

Exemple de sortie:
6,00
4,00
0,00
8,00

Exemples d'explications:
Si N = 2 et M = 0, vous devez continuer à lancer la pièce jusqu'à ce que vous obteniez 2 têtes consécutives. Il n'est pas difficile de montrer qu'en moyenne, 6 lancers de pièces sont nécessaires.
Si N = 2 et M = 1, vous avez besoin de 2 têtes consécutives et vous en avez déjà 1. Vous devez lancer une fois de plus quoi qu'il arrive. Dans ce premier lancer, si vous obtenez des têtes, vous avez terminé. Sinon, vous devez recommencer, car le compteur consécutif se réinitialise, et vous devez continuer à lancer la pièce jusqu'à ce que vous obteniez N = 2 têtes consécutives. Le nombre attendu de lancers de pièces est donc de 1 + (0,5 * 0 + 0,5 * 6) = 4,0 Si N = 3 et M = 3, vous avez déjà 3 têtes, vous n'avez donc plus besoin de lancer.

Toutes les équations mathématiques que j'ai trouvées avaient les bonnes réponses pour les données d'entrée d'échantillon énumérées ci-dessus, mais elles étaient incorrectes pour tous leurs autres ensembles d'entrée (qui ne sont pas connus). Leur solution programmatique semble résoudre le problème bien différemment de ma méthode d'essayer de trouver une équation. Quelqu'un peut-il expliquer comment trouver une équation qui pourrait résoudre ce problème?

probability stochastic-processes markov-process Polshgiant
la source

Voir aussi ici où se trouve également le résultat

donné par Daniel Johnson ci-dessous.

2^{N + 1} - 2^{M + 1}

$2^{N+1}-2^{M+1}$

Dilip Sarwate

Réponses:

Il s'agit d'un exercice de calcul, pensez donc de manière récursive . L'état actuel du retournement des pièces est déterminé par la paire ordonnée avec . Soit le nombre attendu de flips pour atteindre têtes consécutives : $(N,M)$ $N\ge M\ge 0$ $N$ $e(N,M)$

(1) Il y a 50% de chances que le prochain flip soit des têtes, vous amenant à l'état , et 50% de chances que le prochain flip soit des queues, vous amenant à l'état . Cela coûte un flip. Par conséquent, l'attente (récursive) est donnée par $(N,M+1)$ $(N,0)$

e (N, M) = \frac{1}{2} e (N, M + 1) + \frac{1}{2} e (N, 0) + 1.

$e(N,M) = \frac{1}{2} e(N,M+1) + \frac{1}{2} e(N,0) + 1.$

(2) Conditions de base: vous avez déjà stipulé que

e (N, 0) = 2^{N + 1} - 2

$e(N,0) = 2^{N+1}-2$

et évidemment

e (N, N) = 0

$e(N,N) = 0$

(plus de flips ne sont nécessaires).

Voici le programme Mathematica correspondant (y compris la mise en cache des résultats intermédiaires pour accélérer la récursivité, ce qui en fait une solution de programmation dynamique):

e[n_, m_] /; n > m > 0 := e[n, m] = 1 + (e[n, m + 1] + e[n, 0])/2 // Simplify
e[n_, 0] := 2^(n + 1) - 2
e[n_, n_] := 0

Le programme serait similaire dans d'autres langages de programmation qui prennent en charge la récursivité. Mathématiquement, on peut vérifier que simplement en vérifiant la récursivité, car elle vaut évidemment pour les cas de base: $e(N,M) = 2^{N+1} - 2^{M+1}$

2^{N + 1} - 2^{M + 1} = 1 + (2^{N + 1} - 2^{M + 2} + 2^{N + 1} - 2) / 2,

$2^{N+1} - 2^{M+1} = 1 + (2^{N+1} - 2^{M+2} + 2^{N+1} - 2)/2,$

ce qui est vrai pour tout et , QED. $M$ $N$

Plus généralement , la même approche établira que lorsque la pièce a une probabilitéde têtes. La partie difficile élabore la condition de base. Cela se fait en chassant la récurrence deétapes jusqu'à ce que finalementsoit exprimé en termes de lui-même et en résolvant: $e(N,M) = \frac{p^{-N} - p^{-M}}{1-p}$ $p$ $e(N,0)$ $N$ $e(N,0)$

\begin{aligned} e (N, 0) & = 1 + p e (N, 1) + (1 - p) e (n, 0) \\ = 1 + p (1 + p e (N, 2) + (1 - p) e (N, 0)) + (1 - p) e (N, 0) \\ \dots \\ = 1 + p + p^{2} + \dots + p^{N - 1} + (1 - p) [1 + p + \dots + p^{N - 1}] e (N, 0); \\ e (N, 0) & = \frac{1 - p^{N}}{1 - p} + (1 - p^{N}) e (N, 0); \\ e (N, 0) & = \frac{p^{- N} - 1}{1 - p} . \end{aligned}

$\eqalign{ e(N,0) &= 1 + p e(N,1) + (1-p) e(n,0) \\ &= 1 + p\left(1 + p e(N,2) + (1-p) e(N,0)\right) + (1-p) e(N,0) \\ \cdots \\ &= 1 + p + p^2 + \cdots + p^{N-1} + (1-p)[1 + p + \cdots + p^{N-1}]e(N,0);\\ e(N,0) &= \frac{1-p^N}{1-p} + (1-p^N)e(N,0); \\ e(N,0) &= \frac{p^{-N}-1}{1-p}. }$

whuber
la source

Peut -être qu'il serait préférable de travailler de manière itérative plutôt que récursive ? Vous avez

qui donne

et donc

e (N, M) = \frac{1}{2} e (N, M + 1) + \frac{1}{2} e (N, 0) + 1

$e(N,M)=\frac{1}{2}e(N,M+1)+\frac{1}{2}e(N,0)+1$

e (N, M + 1) = 2 e (N, M) - 2^{N + 1}

$e(N,M+1)=2e(N,M)-2^{N+1}$

et ainsi de suite donnant

Ou l'équation de différence pourrait être résolue "théoriquement" plutôt que par itération.

\begin{aligned} e (N, 1) & = 2 e (N, 0) - 2^{N + 1} = 2 (2^{N + 1} - 2) - 2^{N + 1} = 2^{N + 1} - 4 \\ e (N, 2) & = 2 e (N, 1) - 2^{N + 1} = 2 (2^{N + 1} - 4) - 2^{N + 1} = 2^{N + 1} - 8 \end{aligned}

$\begin{align*}e(N,1)&=2e(N,0)-2^{N+1}=2(2^{N+1}-2)-2^{N+1}=2^{N+1}-4\\e(N,2)&=2e(N,1)-2^{N+1}=2(2^{N+1}-4)-2^{N+1}=2^{N+1}-8\end{align*}$

e (N, M) = 2^{N + 1} - 2^{M + 1} .

$e(N,M)=2^{N+1}-2^{M+1}.$

Dilip Sarwate

@Dilip Les inférences que vous tirez à la fois sur "qui donne" et "et ainsi de suite" sont récursives. Quelle méthode de solution envisagez-vous par "résolu théoriquement"?

whuber

x (n) = 2 x (n - 1), x (0) = 1,

$x(n)=2x(n-1),~~ x(0)=1,$

x (n)

$x(n)$

x (n) = 2 x (n - 1) = 2 (2 x (n - 2)) = 2 (2 (2 x (n - 3))) = \dots = 2 (2 (\dots 2 x (0) \dots) = 2^{n}

$x(n)=2x(n-1)=2(2x(n-2))=2(2(2x(n-3)))=\cdots=2(2(\cdots 2x(0)\cdots)=2^n$

x (0) = 1 \Rightarrow x (1) = 2 x (0) = 2 \Rightarrow x (2) = 2 x (1) = 2^{2} \Rightarrow \dots x (n) = 2 x (n - 1) = 2 \cdot 2^{n - 1} = 2^{n} .

$x(0)=1\Rightarrow x(1)=2x(0)=2\Rightarrow x(2)=2x(1)=2^2\Rightarrow \cdots x(n)=2x(n-1)=2\cdot 2^{n-1}=2^n.$

find_x(n)if n=0 return 1 else return 2*find_x(n-1)find_x

n

$n$ y = 1; while n > 0 do begin y=2*y; n=n-1 end; return y

Si vous regardez comment ces programmes sont réellement implémentés sur l'ordinateur, @Dilip, dans de nombreux environnements (tels que R), ils ne diffèrent guère du tout. (Dans un cas, vous créez puis traitez un vecteur 1:net dans l'autre, vous découvrirez qu'il n:1a été placé sur la pile et traité à l'envers.) Mais une partie de mon argumentation était conceptuelle : votre commentaire initial parlait de "travailler de manière itérative". Cela faisait référence à l' analyse et non à un programme informatique. Mais ce sont des points triviaux et tangentiels dont la discussion ne justifie pas d'étendre ce fil de commentaires.

whuber

Pour résoudre ce problème, j'utiliserai des processus stochastiques, des temps d'arrêt et une programmation dynamique.

Tout d'abord, quelques définitions:

X_{n} ≐ # (of consecutive heads after the nth flip)

$X_n \doteq \#\text{(of consecutive heads after the nth flip)}$

X_{0}

$X_0$

X_{0} = 0

$X_0 = 0$

X

$X$

X_{0} = M

$X_0 = M$

τ_{N} ≐ min {k : X_{k} = N} and τ_{0} ≐ min {k > 1 : X_{k} = 0}

$\tau_N \doteq \min\{k: X_k = N\} \text{ and } \tau_0 \doteq \min\{k > 1: X_k = 0\}$

$\tau_N$ $(X_{\tau_N} = N)$ $(X_0 = M)$ $M \leq N$

E [τ_{N} | X_{0} = M] = E [τ_{N} 1_{{τ_{N} < τ_{0}}} + τ_{N} 1_{{τ_{N} > τ_{0}}} | X_{0} = M]

$E[\tau_N|X_0 =M] = E[\tau_N\boldsymbol{1}_{\{\tau_N < \tau_0\}} + \tau_N\boldsymbol{1}_{\{\tau_N > \tau_0\}}|X_0 =M]$

= (N - M) (\frac{1}{2})^{N - M} + E [τ_{0} | τ_{N} > τ_{0}, X_{0} = M] + (1 - (\frac{1}{2})^{N - M}) E [τ_{N} | X_{0} = 0]

$= (N-M)(\frac{1}{2})^{N-M} + E[\tau_0|\tau_N > \tau_0,X_0 =M] + (1 - (\frac{1}{2})^{N-M})E[\tau_N|X_0 = 0]$

Le premier correspond au nombre attendu de flips avant d'obtenir une queue en supposant qu'une queue est retournée avant que N têtes consécutives soient observées en supposant que nous commençons avec M têtes consécutives. Il n'est pas trop difficile de voir que

E [τ_{0} | τ_{N} > τ_{0}, X_{0} = M] = \sum_{j = 1}^{N - M} (j) (\frac{1}{2})^{j} = 2 - (N - M + 2) (\frac{1}{2})^{N - M}

$E[\tau_0|\tau_N > \tau_0,X_0 =M] = \sum^{N-M}_{j=1}(j)(\frac{1}{2})^j = 2 - (N-M+2)(\frac{1}{2})^{N-M}$

Maintenant, tout ce que nous avons à faire est de calculer la deuxième attente conditionnelle qui correspond au nombre attendu de flips nécessaires pour observer N têtes consécutives à partir de 0. Avec des calculs similaires, nous voyons que

E [τ_{N} | X_{0} = 0] = E [τ_{N} 1_{{τ_{N} < τ_{0}}} + τ_{N} 1_{{τ_{N} > τ_{0}}} | X_{0} = 0]

$E[\tau_N|X_0 = 0] = E[\tau_N\boldsymbol{1}_{\{\tau_N < \tau_0\}} + \tau_N\boldsymbol{1}_{\{\tau_N > \tau_0\}}|X_0 =0]$

= N (\frac{1}{2})^{N} + E [τ_{0} | τ_{N} > τ_{0}, X_{0} = 0] + (1 - (\frac{1}{2})^{N}) E [τ_{N} | X_{0} = 0]

$= N(\frac{1}{2})^{N} + E[\tau_0|\tau_N > \tau_0,X_0 =0] + (1 - (\frac{1}{2})^N)E[\tau_N|X_0 = 0]$

= 2^{N} {N (\frac{1}{2})^{N} + (2 - (N + 2) (\frac{1}{2})^{N})}

$= 2^N\lbrace N(\frac{1}{2})^{N} + (2 - (N+2)(\frac{1}{2})^{N})\rbrace$

= 2^{N + 1} - 2

$= 2^{N+1} - 2$

Cela donne une réponse finale de:

E [τ_{N} | X_{0} = M] = (N - M) (\frac{1}{2})^{N - M} + 2 - (N - M + 2) (\frac{1}{2})^{N - M} + (1 - (\frac{1}{2})^{N - M}) (2^{N + 1} - 2)

$E[\tau_N|X_0 =M] = (N-M)(\frac{1}{2})^{N-M} + 2 - (N-M+2)(\frac{1}{2})^{N-M} + (1 - (\frac{1}{2})^{N-M})(2^{N+1} - 2)$

= 2^{N + 1} - 2^{M + 1}

$= 2^{N+1}-2^{M+1}$

Cela correspond aux quatre cas de test que vous avez répertoriés. Avec une réponse aussi simple, il peut y avoir un moyen plus simple de calculer cela.

Daniel Johnson
la source

Il s'agit d'un moyen plus difficile à résoudre que l'idée récursive répertoriée ci-dessus, mais il est extrêmement utile de voir les deux approches présentées ensemble. La plupart des gens n'apprécient pas la façon dont les méthodes d'arrêt peuvent également être utilisées pour de petits problèmes pratiques.

Avertissement: ce qui suit peut ne pas être considéré comme une bonne réponse dans la mesure où il ne fournit pas une solution de forme fermée à la question, en particulier. par rapport aux réponses précédentes . J'ai cependant trouvé l'approche suffisamment intéressante pour élaborer la distribution conditionnelle.

$N$ $k$ $1-p(N,k)$

p (N, k) = {\begin{cases} 1 & if k < N \\ \sum_{m = 1}^{N} \frac{1}{2^{m}} p (N, k - m) & else \end{cases}

$p(N,k) = \begin{cases} 1 &\text{if } k<N\\ \sum_{m=1}^{N} \frac{1}{2^m}p(N,k-m) &\text{else}\\ \end{cases}$

N

$N$

k

$k$

N

$N$

N

$N$

$m\ge N$

     p(N,m-N-1) \dfrac{1}{2^{N+1}} &\text{if } N<m<2N+1
     \end{cases}

$m-N-1$ $N$ $N$ $m-N-1$

$M$ $N$ $m\ge N$

     0 &\text{if } N<m\le N+M\\

      \dfrac{1}{2^{M}}\sum_{r=M+1}^{N}\dfrac{1}{2^{r-M}}q(N,m-r)&\text{if } N+M<m

H e n c e t h e c o n d i t i o n a l p r o b a b i l i t y o f w a i t i n g $ m $ s t e p s t o g e t $ N $ c o n s e c u t i v e h e a d s g i v e n t h e f i r s t $ M $ c o n s e c u t i v e h e a d s i s

$Hence the conditional probability of waiting $m$ steps to get $N$ consecutive heads given the first $M$ consecutive heads is$

T h e e x p e c t e d n u m b e r o f d r a w s c a n t h e n b e d e r i v e d b y

$The expected number of draws can then be derived by$

E (M, N) - M

$\mathfrak{E}(M,N)-M$ pas...

Xi'an
la source