Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
3  
Just to clarify the question, does TTTT have three runs of length two, or none? –  James Martin Jan 17 '13 at 11:46
    
And is $P(j,k,n)$ for exactly $j$ runs or at least $j$ runs? –  Brendan McKay Jan 17 '13 at 13:42
add comment

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
Nice explanation. Regarding this: "provided the median grows at some reasonable rate (and it looks like it should be linear in n, or almost that)" -- in this case the mean is about $\log_2 n $, is that "reasonable" would you say? –  Bjørn Kjos-Hanssen Apr 30 at 14:18
    
@BjørnKjos-Hanssen, there are two steps, and we're interested in the mean/median of a different quantity at each stage. At the first stage we ask how many runs of length $k$ there are. Provided the median of this random variable is large, it will be tightly concentrated. ("Large" here just means large enough to make the exponential bounds decay to zero, so larger than $k$ or $k^3$.) In this case the median is linear in $n$, so if $k$ is growing slower than this we will get concentration. –  Ben Barber Apr 30 at 14:59
    
The second step is to decide whether the value we are concentrated near is 0 or something larger than 1. This is always problem dependent: in this case the expected number of runs of length $k$ is around $n2^{-k}$, so the threshold will be around $\log_2 n$. But to be completely explicit, this isn't the value that we wanted to be reasonably large. –  Ben Barber Apr 30 at 15:00
    
Oh right it was the number of runs not the length of the longest run –  Bjørn Kjos-Hanssen Apr 30 at 15:59
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.