Cross validated question

Another problem generated by X’validated (on which I spent much too much time!): given an unbiased coin that produced M heads in the first M tosses, what is the expected number of additional tosses needed to get N (N>M) consecutive heads?

Consider the preliminary question of getting a sequence of N heads out of k tosses, with probability 1-p(N,k). The complementary probability is given by the recurrence formula
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}
Indeed, my reasoning is that the event of no consecutive N heads out of k tosses can be decomposed according to the first occurrence of a tail out of the first N tosses. Conditioning on whether this first tail occurs at the first, second, …, nth draw leads to this recurrence relation. As I wanted to make sure, I rand the following R code

#no sequence of length N out of k draws
pnk=function(N,k){
  if (k<N){
       p=1}
  else{
    p=0
    for (j in 1:N)
      p=p+pnk(N,k-j)/2^j
      }
  return(p)
  }

and got the following check:

 > k=15
> #N=2
> 1-pnk(2,k)-sum(apply(vale[,-1]*vale[,-k],1,max))/10^6
[1] 6.442773e-05
> #N=3
> 1-pnk(3,k)-sum(apply(vale[,-(1:2)]*vale[,-c(1,k)]*vale[,-((k-1):k)],1,max))/10^6
[1] 0.0004090137

Next, the probability of getting the first consecutive N heads in m≥ N tosses is
q(N,m) =\begin{cases}  0 &\text{if }m<N\\  \frac{1}{2^N} &\text{if }m=N\\  \frac{p(N,m-N-1) }{2^{N+1}} &\text{if } N<m\\  \end{cases}
Both first cases are self-explanatory. the third case corresponds to a tail occurring at the m−N−1th draw, followed by N heads, and prohibiting N consecutive heads prior to the m−N−1th toss. When checking by

Tsim=10^7
S=sample(c(0,1),Tsim,rep=TRUE)
SS=S[-Tsim]*S[-1]
out=NULL
i=2
while (i<=length(SS)){
  if ((SS[i]==1)&&(SS[i-1]==1)){
     out=c(out,i);i=i+1}
   i=i+1}
dif=diff((1:length(SS[-out]))[SS[-out]==1])
trobs=probs=tabulate(dif+(dif==1))/length(dif)[1:20]
for (t in 1:20) trobs[t]=qmn(2,t)
barplot(probs,col="orange2",ylim=c(-max(probs),max(probs)))
barplot(-trobs[1:20],col="wheat",add=TRUE)

I however get a discrepancy shown in the above graph for the cases m=3,4, and N=2, which is due to the pseudo-clever way I compute the waiting times, removing the extra 1’s… Because the probabilities to wait 3 and 4 times for 2 heads should really be both equal to 1/2³. And things agree after that.

Now, the probability to get M heads first and N heads in m≥ N tosses (and no less) is
r(M,N,m) = \begin{cases}  \frac{1}{2^N} &\text{if }m=N\\  0 &\text{if } N<m\le N+M\\  \sum_{r=M+1}^{N}\frac{q(N,m-r)}{2^{r}}&\text{if } m> N+M  \end{cases}

The third case is explained by the fact that completions of the first sequence of heads must stop (by a tail) before reaching N heads. Hence the conditional probability of waiting m tosses to get N consecutive heads given the first M consecutive heads is

s(M,N,m) = \begin{cases}  \frac{1}{2^{N-M}} &\text{if }m=N\\  0 &\text{if } N<m\le N+M\\  \sum_{r=M+1}^{N}\frac{q(N,m-r)}{2^{r-M}}&\text{if } m> N+M  \end{cases}
The expected number can then be derived by

\mathfrak{E}(M,N)= \sum_{m=N}^\infty m\, s(M,N,m)

or

\mathfrak{E}(M,N)-M

for the number of *additional* steps…

Checking for the smallest values of M and N, I got a reasonable agreement with the theoretical value of 2N+1-2M+1(established on Cross validated). (For larger values of M and N, I had to replace the recursive definition of pnk with a matrix computed once for all.)

3 Responses to “Cross validated question”

  1. [...] Xi’an’s Og studies a CrossValidated.SE question. [...]

  2. Is it possible with today’s manufacturing processes to produce a unbiased coin?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 680 other followers