6
$\begingroup$

Inspired by This topic:

Let there be $N$ balls in a straight line. We colour them with $m$ $(c_1, c_2,\ldots , c_m)$ different colours.

Determine the probability there exists at least one streak of monochromatic balls of at least length $1\leq k\leq N$.

The real question here is, how do we count how many of the colourings are desirable to us and how many there are in total.

For instance, pick $N=5, m=2$ (equal probability), $k=3$. With two colours, there should be $2^5 = 32$ different colourings.

EDIT: Thanks Arthur
$5$ ways for three consecutive to occur, $2$ ways for four consecutives and $1$ way of five consecutives. By symmetry, there should be $16$ desirable choices.

With some modifications we can also work out the solution if the colourings had different probabilities.

Question: How do we count desirable choices when $N=100, m=2$ (equal probability) and $k = 5$? It's not very sensible to count each case. Is there a way to work this problem out with pen and paper?

$\endgroup$
  • 3
    $\begingroup$ An example of the technique is described here: math.stackexchange.com/questions/4658/… $\endgroup$ – Qiaochu Yuan Aug 2 '17 at 6:08
  • 1
    $\begingroup$ There are actually five ways for three consecutives to occur: $11121, 11122, 21112, 12111, 22111$. And then, of course, you have the five ways for three consecutive $2$'s to occur as well. $\endgroup$ – Arthur Aug 2 '17 at 6:15
  • $\begingroup$ @Arthur I blame the mornings :D Thanks for pointing that out. $\endgroup$ – Alvin Lepik Aug 2 '17 at 6:25
3
$\begingroup$

There are $m^N= 2^{100}$ cases in total.
There are $1231762993555129375668495000350$ desirable cases.

To count each the desirable cases exactly once you can do this for all $i\in[k,N]$:

  1. Choose a common color for the balls with position $i-k+1$ to $i$. Count a factor $m$
  2. Choose any color for the balls with position $i+1$ to $N$. Count a factor $m^{N-i}$
  3. Partition (with ordering) the balls with position $1$ to $i-k$ into groups of size $1$ to $k-1$. E.g. for $i=9,k=5$ the valide group sizes are $\quad\{\{4\},\{3,1\},\{1,3\},\{2,2\},\{2,1,1\},\{1,2,1\},\{1,1,2\},\{1,1,1,1\}\}$
    For each partition the last group must have a color different from that of step 1. The second last group must have a color different from the last group etc. Hence a given partition yields $(m-1)^q$ cases, where $q$ is a group count. In total we get a factor $S=\sum_q(m-1)^q$. For the example ($i=9,k=5$) we have $q=1,2,2,2,3,3,3,4$

The sum depends on variables $k$, $i$ and constant $m$. We have

$S(1, i) = \max(2-i, 0) \\S(k, i)=\begin{cases} S(k-1,i-1)& k\leq i\leq 2 k-2 \\ (m-1)\sum_{j=1}^{k-1}S(k,i-j)& \text{else} \end{cases}$

To get the result multiply the factors and sum over $i$: $$\sum_{i=k}^N S(k,i)m^{N-i+1}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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