Runs in coin flips

Question

Let $P(j,k,n)$ be the probability of getting $j$ uniform runs of length $k$ from $n$ fair coin flips. What's the best way to compute $P$? I have no idea how difficult it might be; if it's a very complicated combinatorial argument, I'm looking more to understand the mathematical tools than to actually be able to do this explicitly in nontrivial cases. If anyone wants to show off, is $P(j,k,n,\alpha)$ for $\alpha \in [0,1]$ the weight of the coin much harder?

Answer 1

For large $n$, this sort of question can be tackled via concentration of measure. The idea is that the typical case should be very close to the average case, so that the probability is essentially either zero or one, depending on whether the property holds on average.

One useful tool is Talagrand's inequality. Let $\Omega = \Omega_1 \times \cdots \times \Omega_n$ be a product space and let $X$ be a random variable on $\Omega$ satisfying

1. $|X(\omega) - X(\omega')| \leq c$ whenever $\omega$ differs from $\omega'$ on a single coordinate. ($X$ doesn't vary too quickly.)
2. Whenever $X(\omega) \geq t$ there is a set $I$ of $f(t)$ coordinates such that $X(\omega') \geq t$ for every $\omega'$ agreeing with $\omega$ on $I$. (If $X$ is large then there is a small certificate showing why this is the case.)

Let $m$ be the median of $X$. Then Talagrand's inequality states that $\mathbb{P}(|X-m| \geq \epsilon m) \leq 4 \exp(-\frac{\epsilon^2m^2}{4f(m)c^2})$.

If the concentration is good, then the median will in fact be close to the mean $\mu$, so there is a similar (slightly more complicated) inequality in terms of $\mu$. (This is worked out carefully in Molloy and Reed's Graph colouring and the probabilistic method.)

Let $X$ be the number of runs of length $k$ in $n$ trials. There are two possible interpretations of your question, depending on whether you want the runs to be disjoint. In either case we have $f(t) = kt$, as the $t$ runs of length $k$ are themselves a certificate.

In the case where the runs must be disjoint we can take $c=1$, so the factor on the right hand side becomes $4 \exp(-\frac{\epsilon^2m}{4k})$. So provided the median grows at some reasonable rate (and it looks like it should be linear in $n$, or almost that) there is very tight concentration of $X$ around a single value, and your $P$ is either approximately 0 or approximately 1 for large $n$ and almost all values of $j$.

If the runs do not need to be disjoint then we can take $c=k$ so that the right hand side becomes $4 \exp(-\frac{\epsilon^2m}{4k^3})$. Again, provided $m$ grows, concentration is good and there is a sharp threshold for $j$ at which the probability rapidly goes from $\approx 1$ to $\approx 0$ as $j$ increases.

The only place $\alpha$, the probability of success, enters this picture is in the calculation of the median.

This doesn't say anything about how to calculate the median (or mean), but that usually turns out to be easier than calculating the probabilities of interest directly.

Answer 2

Here's a short blog post on expected maximum run length with a reference to a longer but still accessible paper. You could use the techniques in the paper to study more than maximum run length.