Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose we have a row of $c\,W$ elements. We select half of them, $\displaystyle \frac{c\,W}{2}$. What is the probability that we have at least one run of at least $W$ selected elements, in terms of $c$ and $W$?

EDIT: $c$ and $W$ are both positive integers.

share|cite|improve this question
I assume you mean we select half of them randomly with uniform distribution? And you're implying that $cW$ is even? – joriki Jun 10 '11 at 1:09
Yes, we select exactly half of them uniformly at random. We can assume $cW$ is even as well. – Gautam Kamath Jun 10 '11 at 1:17
If you want to be more specific, you can assume $c$ is even, and $W$ is arbitrary. – Gautam Kamath Jun 10 '11 at 1:36
What is the distribution of the elements? Are they uniform? Normal? Do you shuffle the elements when you select them, or keep them in the original order? I'm asking because e.g. if they are such that $x_i<x_j$ when $i<j$ and you keep the original order, then the probability of a run of $W$ elements is 1 whenever $c\geq 2$. – Chris Taylor Jun 10 '11 at 8:04
up vote 1 down vote accepted

The following assumes that $W$ and $a$ are positive integers, that one chooses uniformly at random $aW$ integers between $1$ and $2aW$, and that one asks for the probability of the event $A$ that the resulting set $S$ contains at least $W$ consecutive integers.

Let us compute the probability of the event $A_i$ that $S$ contains the $W$ consecutive integers starting from $i$. Then $A_i=\emptyset$ if $i\ge(2a-1)W+2$, otherwise $S$ is determined by its $(a-1)W$ elements not between $i$ and $i+W-1$. Hence $$ P(A_i)=\frac{{(2a-1)W\choose (a-1)W}}{{2aW\choose aW}}=p(W). $$ Similar formulas can be written for $P(A_i\cap A_j)$ for example, depending of $|i-j|$.

Since $A$ is the union of the events $A_i$, an exact formula for $P(A)$ is given by the exclusion-inclusion formula, and an easy upper bound is $$ P(A)\le(2a-1)Wp(W). $$ When $W\to+\infty$, Stirling formula yields $$ p(W)=\sqrt{\frac{2a-1}{2a-2}}(C_a)^W(1+o(1)),\quad C_a=(2a-1)^{2a-1}2^{-2a}a^{-a}(a-1)^{1-a}. $$ Roughly speaking, the error made in the uper bound is to count several times the segments of length greater than $W$ included in $S$. This remark and some heuristic arguments suggest that a discount of $\displaystyle\frac{a}{2a-1}$ should be applied to the upper bound, hence $$ P(A)=a\sqrt{\frac{2a-1}{2a-2}}W(C_a)^W(1+o(1)). $$

share|cite|improve this answer

Your Answer


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.