4
$\begingroup$

Given $n$ flips of a coin with success probability $p$, what is the expected number of $k$-length win streaks in $n$?

(I've looked for this question online, but the answers always restrict $n$ to be a power of $2$ or $k$ to be written in terms of $\log$ base $2$. Refrain from that here, if possible.)

$\endgroup$
2
  • $\begingroup$ Do we consider a k+1-length streak to be two overlapping k-length streaks? $\endgroup$
    – gregkow
    Feb 14, 2014 at 19:06
  • $\begingroup$ No, consider it only a k+1-length streak. Assume a sequence of wins and losses is: WWLLLLWWW, the tally of streaks would be: wins = 1 two-streak, 1 three-streak; losses = 1 four-streak. Given the answer to the above problem, are these equal to our expectations? $\endgroup$ Feb 14, 2014 at 19:39

1 Answer 1

4
$\begingroup$

Suppose that $n\ge k+2$. We assume that "winning streak of length $k$" means a sequence of wins that has length exactly $k$. It either (i) begins with the first toss, and is ended by a loss on the $(k+1)$-th toss or (ii) ends with a win on the last toss, or (iii) is bracketed by losses.

Let $W$ be the number of winning streaks of length $k$ that are bracketed by losses. We find $E(W)$. Define random variable $X_i$ by $X_i=1$ if we have a loss at time $i$, followed by $k$ wins, followed by a loss. Let $X_i=0$ otherwise.

Note that for $1\le i\le n-k-1$, we have $\Pr(X_i=1)=(1-p)^2p^k$. For larger $i$, we have $\Pr(X_i=1)=0$. We have $W=\sum X_i$, and therefore by the linearity of expectation $$E(W)=(n-k-1)(1-p)^2p^k.$$ Add to this the expected number of $k$-streaks that begin with the first toss, or continue until the last toss.

$\endgroup$
2
  • $\begingroup$ What's the expected number of k-length streaks that begin with the first toss or continue until the last toss? $\endgroup$ Feb 14, 2014 at 19:42
  • $\begingroup$ Note we are assuming $n\ge k+2$. For the first kind, we have $(1-p)p^k$, for the second kind the same. $\endgroup$ Feb 14, 2014 at 19:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .