expected number of flips until $k$ consecutive misses or number of flips finish

Question

I followed the argument given in the answers for this question to find the expected number of misses in a sequence of coin-tosses with success probability $p$. The stopping condition for tossing is either until the $k^{th}$ consecutive miss or until the number of rounds reach $n$, whichever comes first. We can consider tail as a miss and head as hit.

The question in the link differs from my question. In my question stopping happens only when $k$ consecutive miss happens or rounds reach $n$. In the linked question stopping happens when $k$ miss happens.

The probability that $k^{th}$ consecutive miss happen at $i^{th}$ trial can not be simply represent in terms of $i$ and $k$ as the number of hits or misses before the start of the sub-sequence of $k$-consecutive miss is still unknown. There can be many misses and hits before the start of the sub-sequence which results in stopping. Similarly there can be unknown number of misses or hits before reaching the end of round ($n$).

Is it even possible to represent this number in a closed form ? Any help and suggestions ?

Answer 1

Consider first an auxilary problem. In how many ways can we arrange $b$ black balls and $w$ white balls so that every sequence of black balls is shorter than $B$?

The problem is equivalent to that of placing $b$ balls into $w+1$ bins of the capacity $B-1$ balls each. The problem has very well-known solution: $$ N(w,b,B)=\sum_{i\ge0}(-1)^i\binom{w+1}i\binom{b+w-Bi}w,\tag1 $$ with the convention $\binom nk=0$ for $n<0$.

Using this one obtains the following expression for the expected number of rounds in your problem: $$\sum_{i=0}^n n\,N(i,n-i,k)p^i(1-p)^{n-i}+\sum_{l=k}^n l\,\sum_{i=0}^{l-k} N(i-1,l-k-i,k)p^i(1-p)^{l-i},\tag2$$ where the first term accounts for the events where no $k$-row of misses happens until reaching the $n$-th round, whereas the second term accounts for the events where $l-k-1$ rounds ($k+1\le l\le n$) with no $k$-row of misses is followed by a single hit and the $k$-row of misses ($i$ in both sums counts the number of hits). To incorporate into the second sum the event with no hit (pure $k$-row of misses) we redefine $N$ for the case $w=-1,b=0$: $$N(-1,0,B)=1. $$

Answer 2

Hint(very detailed hint): Let $A(n)$ be the probability to have $n$ trials where you can not miss more than $k-1$ times. Then, you will have that $$\mathbb{E}[X]=nA(n)+\sum _{i=k}^ni\cdot P(X=i)=nA(n)+k\cdot (1-p)^k+\sum _{i=k+1}^ni\cdot p\cdot (1-p)^kA(i-k-1).$$ Now, you can get a closed form for $A(m)$ by factoring the misses and the success in the following way, suppose a miss is denoted by $1$ and a success is denoted by $0,$ then $$0^c1^{a_1}0^{b_1}1^{a_1}\cdots 0^{b_{j-1}}1^{a_j}0^d,$$ where the $1\leq a_i<k$ and $1\leq b_j$ and $0\leq c+d,$ and $$\sum a_s,\, c+d+\sum b_s=b.$$
So fix the number of misses to be $\ell$ then $$A(m)=\sum _{\ell =0}^m\mathcal{A}(\ell,m-\ell)(1-p)^{\ell}p^{m-\ell},$$ where $\mathcal{A}(a,b)$ is the number of ways you can have $a$ misses and $b$ succeses where each chunk of misses has less than $k$ consecutive misses.

To get $\mathcal{A}(a,b)$ consider the number of chunks (consecutive misses) that you can have, call this $j$ then $$\mathcal{A}(a,b)=\sum _{j = 1}^a\text{#ways to have $a$ misses and $b$ successes with exactly $j$ chunks}.$$ Notice that now we can use Stars and Bars because we are trying to place the $a$ misses in $j$ boxes(also inclusion exclusion, cause they have to be less than $k$) and you have to place the $b$ successes in $j+1$ boxes with some conditions, also possible using Stars and Bars. Use multiplication principle.

Answer 3

When $p=1/2$, the required expectation can be written in terms of the Fibonacci $n$-step numbers. Let $T$ denote the number of trials until $k$ consecutive tails. Then $$ \mathsf{P}(T>i)=\frac{F_{i+2}^{(k)}}{2^i}, $$ which is the probability that no runs of $k$ consecutive tails occur in $i$ tosses. Therefore, $$ \mathsf{E}[T\wedge n]=\sum_{i=0}^{\infty}\mathsf{P}(T\wedge n>i)=\sum_{i=0}^{n-1}\mathsf{P}(T\wedge n>i) =\sum_{i=1}^{n}\frac{F_{i+1}^{(k)}}{2^{i-1}}. $$