10 replaced http://stats.stackexchange.com/ with https://stats.stackexchange.com/
source | link

Warning: the following may not be considered as a proper answer in that it does not provide a closed form solution to the question, esp. when compared with the previous answersthe previous answers. I however found the approach sufficiently interesting to work out the conditional distribution.

Consider the preliminary question of getting a sequence of $N$ heads out of $k$ throws, with probability $1-p(N,k)$. This 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 no consecutive $N$ heads out of $k$ draws can be decomposed according to the first occurrence of a tail out of the first $N$ throws. Conditioning on whether this first tail occurs at the first, second, ..., $N$th draw leads to this recurrence relation.

Next, the probability of getting the first consecutive N heads in $m\ge N$ throws is $$ q(N,m) =\begin{cases} \dfrac{1}{2^N} &\text{if }m=N\

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

$$ The first case is self-explanatory. the second case corresponds to a tail occuring at the $m-N-1$th draw, followed by $N$ heads, and the last case prohibits $N$ consecutive heads prior to the $m-N-1$th draw. (The two last cases could be condensed into one, granted!)

Now, the probability to get $M$ heads first and the first consecutive $N$ heads in exactly $m\ge N$ throws (and no less) is $$ r(M,N,m) = \begin{cases} 1/2^N &\text{if }m=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

\end{cases} $$ Hence the conditional probability of waiting $m$ steps to get $N$ consecutive heads given the first $M$ consecutive heads is $$ s(M,N,m) = \begin{cases} 1/{2^{N-M}} &\text{if }m=N\ 0 &\text{if } N \sum_{r=M+1}^{N}\dfrac{q(N,m-r)}{2^{r-M}}&\text{if } N+M

\end{cases} $$ The expected number of draws 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...

Warning: the following may not be considered as a proper answer in that it does not provide a closed form solution to the question, esp. when compared with the previous answers. I however found the approach sufficiently interesting to work out the conditional distribution.

Consider the preliminary question of getting a sequence of $N$ heads out of $k$ throws, with probability $1-p(N,k)$. This 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 no consecutive $N$ heads out of $k$ draws can be decomposed according to the first occurrence of a tail out of the first $N$ throws. Conditioning on whether this first tail occurs at the first, second, ..., $N$th draw leads to this recurrence relation.

Next, the probability of getting the first consecutive N heads in $m\ge N$ throws is $$ q(N,m) =\begin{cases} \dfrac{1}{2^N} &\text{if }m=N\

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

$$ The first case is self-explanatory. the second case corresponds to a tail occuring at the $m-N-1$th draw, followed by $N$ heads, and the last case prohibits $N$ consecutive heads prior to the $m-N-1$th draw. (The two last cases could be condensed into one, granted!)

Now, the probability to get $M$ heads first and the first consecutive $N$ heads in exactly $m\ge N$ throws (and no less) is $$ r(M,N,m) = \begin{cases} 1/2^N &\text{if }m=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

\end{cases} $$ Hence the conditional probability of waiting $m$ steps to get $N$ consecutive heads given the first $M$ consecutive heads is $$ s(M,N,m) = \begin{cases} 1/{2^{N-M}} &\text{if }m=N\ 0 &\text{if } N \sum_{r=M+1}^{N}\dfrac{q(N,m-r)}{2^{r-M}}&\text{if } N+M

\end{cases} $$ The expected number of draws 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...

Warning: the following may not be considered as a proper answer in that it does not provide a closed form solution to the question, esp. when compared with the previous answers. I however found the approach sufficiently interesting to work out the conditional distribution.

Consider the preliminary question of getting a sequence of $N$ heads out of $k$ throws, with probability $1-p(N,k)$. This 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 no consecutive $N$ heads out of $k$ draws can be decomposed according to the first occurrence of a tail out of the first $N$ throws. Conditioning on whether this first tail occurs at the first, second, ..., $N$th draw leads to this recurrence relation.

Next, the probability of getting the first consecutive N heads in $m\ge N$ throws is $$ q(N,m) =\begin{cases} \dfrac{1}{2^N} &\text{if }m=N\

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

$$ The first case is self-explanatory. the second case corresponds to a tail occuring at the $m-N-1$th draw, followed by $N$ heads, and the last case prohibits $N$ consecutive heads prior to the $m-N-1$th draw. (The two last cases could be condensed into one, granted!)

Now, the probability to get $M$ heads first and the first consecutive $N$ heads in exactly $m\ge N$ throws (and no less) is $$ r(M,N,m) = \begin{cases} 1/2^N &\text{if }m=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

\end{cases} $$ Hence the conditional probability of waiting $m$ steps to get $N$ consecutive heads given the first $M$ consecutive heads is $$ s(M,N,m) = \begin{cases} 1/{2^{N-M}} &\text{if }m=N\ 0 &\text{if } N \sum_{r=M+1}^{N}\dfrac{q(N,m-r)}{2^{r-M}}&\text{if } N+M

\end{cases} $$ The expected number of draws 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...

    Post Undeleted by Xi'an
9 added 120 characters in body
source | link

Warning: the following may not be considered as a proper answer in that it does not provide a closed form solution to the question, esp. when compared with the previous answers. I however found the approach sufficiently interesting to work out the conditional distribution.

Consider the preliminary question of getting a sequence of $N$ heads out of $k$ throws, with probability $1-p(N,k)$. This 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 no consecutive $N$ heads out of $k$ draws can be decomposed according to the first occurrence of a tail out of the first $N$ throws. Conditioning on whether this first tail occurs at the first, second, ..., $N$th draw leads to this recurrence relation.

Next, the probability of getting the first consecutive N heads in $m\ge N$ throws is $$ q(N,m) =\begin{cases} \dfrac{1}{2^N} &\text{if }m=N\\ \dfrac{1}{2^N}\dfrac{1}{2} &\text{if } N<m<2N+1\\ p(N,m-N-1) \dfrac{1}{2^N}\dfrac{1}{2} &\text{else} \end{cases} $$$$ q(N,m) =\begin{cases} \dfrac{1}{2^N} &\text{if }m=N\

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

$$ The first case is self-explanatory. the second case corresponds to a tail occuring at the $m-N-1$th$m-N-1$th draw, followed by $N$$N$ heads, and the last case prohibits $N$$N$ consecutive heads prior to the $m-N-1$th$m-N-1$th draw. (The two last cases could be condensed into one, granted!)

Now, the probability to get $M$ heads first and the first consecutive $N$ heads in exactly $m\ge N$ throws (and no less) is $$ r(M,N,m) = \begin{cases} \dfrac{1}{2^N} &\text{if }m=N\\ 0 &\text{if } N<m<N+M\\ \dfrac{1}{2^M}q(N,m-M) &\text{if } N+M\le m<2N-M\\ \dfrac{1}{2^{M+N+1}}\sum_{r=1}^{N-M}\dfrac{1}{2}p(N,m-N-1-M-r)&\text{if } m\ge 2N-M \end{cases} $$$$ Hence the conditional probability of waitingr(M,N,m) = \begin{cases} 1/2^N &\text{if $m$ steps to get}m=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

\end{cases} $$ Hence the conditional probability of waiting $m$ steps to get $N$ consecutive heads given the first $M$ consecutive heads is $$ s(M,N,m) = \begin{cases} 1/{2^{N-M}} &\text{if $N$ consecutive heads given the first}m=N\ 0 &\text{if $M$ consecutive heads is} N $$ s(M,N,m) = \begin{cases} \dfrac{1}{2^{N-M}} &\text{if }m=N\\ 0 &\text{if } N<m<N+M\\ q(N,m-M) &\text{if } N+M\le m<2N-M\\ \dfrac{1}{2N+2}\sum_{r=1}^{N-M}p(N,m-N-1-M-r)&\text{if } m\ge 2N-M \end{cases} $$\sum_{r=M+1}^{N}\dfrac{q(N,m-r)}{2^{r-M}}&\text{if } N+M

\end{cases}

The expected number of draws can then be derived by $$ \mathfrak{E}(M,N)= \sum_{m=N}^\infty m\, s(M,N,m) $$$$ The expected number of draws can then be derived by $$ \mathfrak{E}(M,N)= \sum_{m=N}^\infty m\, s(M,N,m) $$ or $\mathfrak{E}(M,N)-M$$\mathfrak{E}(M,N)-M$ for the number of additional steps...

Consider the preliminary question of getting a sequence of $N$ heads out of $k$ throws, with probability $1-p(N,k)$. This 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 no consecutive $N$ heads out of $k$ draws can be decomposed according to the first occurrence of a tail out of the first $N$ throws. Conditioning on whether this first tail occurs at the first, second, ..., $N$th draw leads to this recurrence relation.

Next, the probability of getting the first consecutive N heads in $m\ge N$ throws is $$ q(N,m) =\begin{cases} \dfrac{1}{2^N} &\text{if }m=N\\ \dfrac{1}{2^N}\dfrac{1}{2} &\text{if } N<m<2N+1\\ p(N,m-N-1) \dfrac{1}{2^N}\dfrac{1}{2} &\text{else} \end{cases} $$ The first case is self-explanatory. the second case corresponds to a tail occuring at the $m-N-1$th draw, followed by $N$ heads, and the last case prohibits $N$ consecutive heads prior to the $m-N-1$th draw. (The two last cases could be condensed into one, granted!)

Now, the probability to get $M$ heads first and the first consecutive $N$ heads in exactly $m\ge N$ throws (and no less) is $$ r(M,N,m) = \begin{cases} \dfrac{1}{2^N} &\text{if }m=N\\ 0 &\text{if } N<m<N+M\\ \dfrac{1}{2^M}q(N,m-M) &\text{if } N+M\le m<2N-M\\ \dfrac{1}{2^{M+N+1}}\sum_{r=1}^{N-M}\dfrac{1}{2}p(N,m-N-1-M-r)&\text{if } m\ge 2N-M \end{cases} $$ Hence the conditional probability of waiting $m$ steps to get $N$ consecutive heads given the first $M$ consecutive heads is $$ s(M,N,m) = \begin{cases} \dfrac{1}{2^{N-M}} &\text{if }m=N\\ 0 &\text{if } N<m<N+M\\ q(N,m-M) &\text{if } N+M\le m<2N-M\\ \dfrac{1}{2N+2}\sum_{r=1}^{N-M}p(N,m-N-1-M-r)&\text{if } m\ge 2N-M \end{cases} $$ The expected number of draws 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...

Warning: the following may not be considered as a proper answer in that it does not provide a closed form solution to the question, esp. when compared with the previous answers. I however found the approach sufficiently interesting to work out the conditional distribution.

Consider the preliminary question of getting a sequence of $N$ heads out of $k$ throws, with probability $1-p(N,k)$. This 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 no consecutive $N$ heads out of $k$ draws can be decomposed according to the first occurrence of a tail out of the first $N$ throws. Conditioning on whether this first tail occurs at the first, second, ..., $N$th draw leads to this recurrence relation.

Next, the probability of getting the first consecutive N heads in $m\ge N$ throws is $$ q(N,m) =\begin{cases} \dfrac{1}{2^N} &\text{if }m=N\

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

$$ The first case is self-explanatory. the second case corresponds to a tail occuring at the $m-N-1$th draw, followed by $N$ heads, and the last case prohibits $N$ consecutive heads prior to the $m-N-1$th draw. (The two last cases could be condensed into one, granted!)

Now, the probability to get $M$ heads first and the first consecutive $N$ heads in exactly $m\ge N$ throws (and no less) is $$ r(M,N,m) = \begin{cases} 1/2^N &\text{if }m=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

\end{cases} $$ Hence the conditional probability of waiting $m$ steps to get $N$ consecutive heads given the first $M$ consecutive heads is $$ s(M,N,m) = \begin{cases} 1/{2^{N-M}} &\text{if }m=N\ 0 &\text{if } N \sum_{r=M+1}^{N}\dfrac{q(N,m-r)}{2^{r-M}}&\text{if } N+M

\end{cases}

$$ The expected number of draws 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...

    Post Deleted by Xi'an
8 deleted 12 characters in body
source | link

Consider the preliminary question of getting a sequence of $N$ heads out of $k$ throws, with probability $1-p(N,k)$. This 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 no consecutive $N$ heads out of $k$ draws can be decomposed according to the first occurrence of a tail out of the first $N$ throws. Conditioning on whether this first tail occurs at the first, second, ..., $N$th draw leads to this recurrence relation.

Next, the probability of getting the first consecutive N heads in $m\ge N$ throws is $$ q(N,m) =\begin{cases} \dfrac{1}{2^N} &\text{if }m=N\\ \dfrac{1}{2^N}\dfrac{1}{2} &\text{if } N<m<2N+1\\ p(N,m-N-1) \dfrac{1}{2^N}\dfrac{1}{2} &\text{else} \end{cases} $$ The first case is self-explanatory. the second case corresponds to a tail occuring at the $m-N-1$th draw, followed by $N$ heads, and the last case prohibits $N$ consecutive heads prior to the $m-N-1$th draw. (The two last cases could be condensed into one, granted!)

Now, the probability to get $M$ heads first and the first consecutive $N$ heads in exactly $m\ge N$ throws (and no less) is $$ r(M,N,m) = \begin{cases} \dfrac{1}{2^N} &\text{if }m=N\\ 0 &\text{if } N<m<N+M\\ \dfrac{1}{2^M}q(N,m-M) &\text{if } N+M\le m<2N-M\\ \dfrac{1}{2^{M+N+1}}\sum_{r=1}^{N-M}\dfrac{1}{2}\{1-p(N,m-N-1-M-r)\}&\text{if } m\ge 2N-M \end{cases} $$$$ r(M,N,m) = \begin{cases} \dfrac{1}{2^N} &\text{if }m=N\\ 0 &\text{if } N<m<N+M\\ \dfrac{1}{2^M}q(N,m-M) &\text{if } N+M\le m<2N-M\\ \dfrac{1}{2^{M+N+1}}\sum_{r=1}^{N-M}\dfrac{1}{2}p(N,m-N-1-M-r)&\text{if } m\ge 2N-M \end{cases} $$ Hence the conditional probability of waiting $m$ steps to get $N$ consecutive heads given the first $M$ consecutive heads is $$ s(M,N,m) = \begin{cases} \dfrac{1}{2^{N-M}} &\text{if }m=N\\ 0 &\text{if } N<m<N+M\\ q(N,m-M) &\text{if } N+M\le m<2N-M\\ \dfrac{1}{2N+2}\sum_{r=1}^{N-M}\{1-p(N,m-N-1-M-r)\}&\text{if } m\ge 2N-M \end{cases} $$$$ s(M,N,m) = \begin{cases} \dfrac{1}{2^{N-M}} &\text{if }m=N\\ 0 &\text{if } N<m<N+M\\ q(N,m-M) &\text{if } N+M\le m<2N-M\\ \dfrac{1}{2N+2}\sum_{r=1}^{N-M}p(N,m-N-1-M-r)&\text{if } m\ge 2N-M \end{cases} $$ The expected number of draws 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...

Consider the preliminary question of getting a sequence of $N$ heads out of $k$ throws, with probability $1-p(N,k)$. This 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 no consecutive $N$ heads out of $k$ draws can be decomposed according to the first occurrence of a tail out of the first $N$ throws. Conditioning on whether this first tail occurs at the first, second, ..., $N$th draw leads to this recurrence relation.

Next, the probability of getting the first consecutive N heads in $m\ge N$ throws is $$ q(N,m) =\begin{cases} \dfrac{1}{2^N} &\text{if }m=N\\ \dfrac{1}{2^N}\dfrac{1}{2} &\text{if } N<m<2N+1\\ p(N,m-N-1) \dfrac{1}{2^N}\dfrac{1}{2} &\text{else} \end{cases} $$ The first case is self-explanatory. the second case corresponds to a tail occuring at the $m-N-1$th draw, followed by $N$ heads, and the last case prohibits $N$ consecutive heads prior to the $m-N-1$th draw. (The two last cases could be condensed into one, granted!)

Now, the probability to get $M$ heads first and the first consecutive $N$ heads in exactly $m\ge N$ throws (and no less) is $$ r(M,N,m) = \begin{cases} \dfrac{1}{2^N} &\text{if }m=N\\ 0 &\text{if } N<m<N+M\\ \dfrac{1}{2^M}q(N,m-M) &\text{if } N+M\le m<2N-M\\ \dfrac{1}{2^{M+N+1}}\sum_{r=1}^{N-M}\dfrac{1}{2}\{1-p(N,m-N-1-M-r)\}&\text{if } m\ge 2N-M \end{cases} $$ Hence the conditional probability of waiting $m$ steps to get $N$ consecutive heads given the first $M$ consecutive heads is $$ s(M,N,m) = \begin{cases} \dfrac{1}{2^{N-M}} &\text{if }m=N\\ 0 &\text{if } N<m<N+M\\ q(N,m-M) &\text{if } N+M\le m<2N-M\\ \dfrac{1}{2N+2}\sum_{r=1}^{N-M}\{1-p(N,m-N-1-M-r)\}&\text{if } m\ge 2N-M \end{cases} $$ The expected number of draws 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...

Consider the preliminary question of getting a sequence of $N$ heads out of $k$ throws, with probability $1-p(N,k)$. This 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 no consecutive $N$ heads out of $k$ draws can be decomposed according to the first occurrence of a tail out of the first $N$ throws. Conditioning on whether this first tail occurs at the first, second, ..., $N$th draw leads to this recurrence relation.

Next, the probability of getting the first consecutive N heads in $m\ge N$ throws is $$ q(N,m) =\begin{cases} \dfrac{1}{2^N} &\text{if }m=N\\ \dfrac{1}{2^N}\dfrac{1}{2} &\text{if } N<m<2N+1\\ p(N,m-N-1) \dfrac{1}{2^N}\dfrac{1}{2} &\text{else} \end{cases} $$ The first case is self-explanatory. the second case corresponds to a tail occuring at the $m-N-1$th draw, followed by $N$ heads, and the last case prohibits $N$ consecutive heads prior to the $m-N-1$th draw. (The two last cases could be condensed into one, granted!)

Now, the probability to get $M$ heads first and the first consecutive $N$ heads in exactly $m\ge N$ throws (and no less) is $$ r(M,N,m) = \begin{cases} \dfrac{1}{2^N} &\text{if }m=N\\ 0 &\text{if } N<m<N+M\\ \dfrac{1}{2^M}q(N,m-M) &\text{if } N+M\le m<2N-M\\ \dfrac{1}{2^{M+N+1}}\sum_{r=1}^{N-M}\dfrac{1}{2}p(N,m-N-1-M-r)&\text{if } m\ge 2N-M \end{cases} $$ Hence the conditional probability of waiting $m$ steps to get $N$ consecutive heads given the first $M$ consecutive heads is $$ s(M,N,m) = \begin{cases} \dfrac{1}{2^{N-M}} &\text{if }m=N\\ 0 &\text{if } N<m<N+M\\ q(N,m-M) &\text{if } N+M\le m<2N-M\\ \dfrac{1}{2N+2}\sum_{r=1}^{N-M}p(N,m-N-1-M-r)&\text{if } m\ge 2N-M \end{cases} $$ The expected number of draws 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...

    Post Undeleted by Xi'an
7 added 80 characters in body
source | link
    Post Deleted by Xi'an
6 added 2 characters in body
source | link
5 added 52 characters in body
source | link
4 added 52 characters in body
source | link
    Post Undeleted by Xi'an
3 added 52 characters in body
source | link
    Post Deleted by Xi'an
2 posted by mistake too early!
source | link
1
source | link