2
$\begingroup$

I have a bag of $n$ balls, $k$ of which are special. This can be thought of as $n-k$ blue balls and $k$ red balls. I now start to pull balls from my bag. When I find my first special ball I start counting. I will count the number of balls until I get my next special ball. For example if I draw to special balls in a row I would have counted to $0$. Once I've drawn my next special ball I start over. Now if I go through all the balls and count the distances between each pulling of a special ball, then what should I expect the largest number I count up to, to be, or what should be the largest expected distance between pulling two special balls?

Edit: To make this more clear, I am pulling balls from my bag and only counting the distance between any two special balls. If I draw $RbbRbbbb$ ($R$ are special or red and $b$ is normal or blue balls), then I would find $2$ to be the number counted.

$\endgroup$
  • $\begingroup$ Looks quite geometric distribution-ish to me... $\endgroup$ – Karn Watcharasupat Dec 12 '17 at 15:37
  • $\begingroup$ Technically the largest possible distance will just be $n$ balls for the case in which all the special balls are at the two extreme ends. I'm not so sure about the expected distance if you are asking for that. $\endgroup$ – Karn Watcharasupat Dec 12 '17 at 15:39
  • $\begingroup$ If $n=15$ and $k=5$ then a possible full draw is $bRRbbbRbRRbbbbb$. What would count as the largest number here? Three for the $b$s in positions $4,5,6$? Four for those plus the next $R$ in position $7$? Five for the $b$s in positions $11,12,13,14,15$? $\endgroup$ – Henry Dec 12 '17 at 15:57
  • $\begingroup$ @KarnWatcharasupat That would be the largest possible, however I doubt that would be average. $\endgroup$ – Benji Altman Dec 12 '17 at 19:45
  • $\begingroup$ @Henry The largest distance in your example would be $3$, as at the end you don't have a red ball, thank you for asking this. I will edit the question accordingly so that it is clear. $\endgroup$ – Benji Altman Dec 12 '17 at 19:46
3
$\begingroup$

A drawing of $n$ balls can be represented by a word in a $2$-letter alphabet. Using techniques of Analytic Combinatorics (by P. Flajolet and R. Sedgewick), we can easily derive the generating function for words in a $\{0,1\}$ alphabet with exactly $k$ $1$'s and such that the longest run of $0$'s between $1$'s is $\leq l$. Symbolically, we have

\begin{align*} {\mathop{SEQ}}(0) \,\,{\mathop{SEQ}}^{=k-1}\left(1\,{\mathop{SEQ}}^{<l+1}(0)\right) \,\,1 \,\,{\mathop{SEQ}}(0), \end{align*}

which, in terms of generating functions, translates to

$$\frac1{1-z}\cdot{\left(z\cdot\frac{1-z^{l+1}}{1-z}\right)}^{k-1}\cdot z\cdot\frac1{1-z}=z^k{\left(\frac1{1-z}\right)}^{2}{\left(\frac{1-z^{l+1}}{1-z}\right)}^{k-1}$$

This allows us to calculate the cumulative distribution function. Indeed, we have that number of draws of $n$ balls, exactly $k$ of which are red, and such that the longest distance between two red balls is at most $l$, is given by

$$\left[z^n\right]\left(z^k{\left(\frac1{1-z}\right)}^{2}{\left(\frac{1-z^{l+1}}{1-z}\right)}^{k-1}\right) = \left[z^{n-k}\right]\left({\left(\frac1{1-z}\right)}^{2}{\left(\frac{1-z^{l+1}}{1-z}\right)}^{k-1}\right),$$

where $\left[z^n\right]\big(f(z)\big)$ denotes the coefficient of $z^n$ in the power series representation for $f$. Moreover, the total number of draws of $n$ balls, exactly $k$ of which are red, is simply $\binom{n}k$. Letting $X$ denote the random variable that returns the longest distance between two red balls we have

$$\mathbb P(X \leq l)=\frac1{\binom{n}k}\cdot \left[z^{n-k}\right]\left({\left(\frac1{1-z}\right)}^{2}{\left(\frac{1-z^{l+1}}{1-z}\right)}^{k-1}\right)$$

Then, since $X$ is non-negative and integer-valued, we have

\begin{align} \mathbb E(X) &=\sum_{l=1}^{n-k}\,\mathbb P(X \geq l)\\ &=\sum_{l=1}^{n-k}\,1-\mathbb P(X \leq l-1)\\ &=(n-k)-\sum_{l=0}^{n-k-1}\,\mathbb P(X \leq l) \end{align}

I reckon it's possible to expand $\left[z^{n-k}\right]\left({\left(\frac1{1-z}\right)}^{2}{\left(\frac{1-z^{l+1}}{1-z}\right)}^{k-1}\right)$ into a more closed form. I will try and do this when I have the time.


First, we write the coefficients $b_{i,l}$ for

$$\sum_{i= 0}^{l(k-1)}b_{i,l}\,z^i ={\left(\frac{1-z^{l+1}}{1-z}\right)}^{k-1}.$$

We have by stars and bars that

$$\frac1{(1-z)^{k-1}}={\left(\sum_{i\geq 0}z^i\right)}^{k-1}=\sum_{i\geq0}\binom{i+k-2}{k-2}\,z^i.$$

Moreover, by Newton's binomial theorem it holds that

$${\left(1-z^{l+1}\right)}^{k-1}=\sum_{i=0}^{k-1}{(-1)}^i\,\binom{k-1}{i}\,z^{i(l+1)}.$$

A simple counting argument then shows that

$$b_{i,l}=\sum_{\displaystyle 0\leq j \leq \left\lfloor \frac{i}{l+1}\right\rfloor}\,{(-1)}^j\,\binom{k-1}j\,\binom{i-j(l+1)+k-2}{k-2}$$

Next, observe that $\frac{1}{{(1-z)}^2}=\sum_{i\geq0}\,(i+1)\,z^i$, so that the coefficient $c_{i,l}$ in

$$\sum_{i\geq 0}\,c_{i,l}\,z^i={\left(\frac1{1-z}\right)}^{2}{\left(\frac{1-z^{l+1}}{1-z}\right)}^{k-1}$$

is given by

$$c_{i,l}=\sum_{j=0}^i b_{j,l}\,(i-j+1)=\sum_{j=0}^{\min(i,l(k-1))}b_{j,l}\,(i-j+1)$$

I'm not sure if $c_{i,l}$ admits further simplification based on the formula for $b_{i,l}$, but I'm pretty satisfied at this point. The end result is

\begin{align} \mathbb E(X) &=(n-k)-\frac1{\binom{n}k}\cdot\sum_{l=0}^{n-k-1}c_{n-k,l}\\ &=(n-k)-\frac1{\binom{n}k}\cdot\sum_{l=0}^{n-k-1} \left( \sum_{j=0}^{\min(n-k,\,l(k-1))} (n-k-j+1)\cdot b_{j,l} \right) \end{align}

where

$$b_{j,l}=\sum_{\displaystyle 0\leq s \leq \left\lfloor \frac{j}{l+1}\right\rfloor} {(-1)}^s\,\binom{k-1}s\,\binom{j-s(l+1)+k-2}{k-2}$$

$\endgroup$
  • $\begingroup$ you might be interested to the other approach to this problem as given in my answer. $\endgroup$ – G Cab Dec 14 '17 at 12:23
  • $\begingroup$ Oops, my simulation had a mistake. I fixed it, and results seem consistent with the theoretical answer above. I am pretty confident in it now. $\endgroup$ – Fimpellizieri Dec 14 '17 at 18:35
  • $\begingroup$ by $z^{n-k}$ I suppose you mean $[z^{n-k}]$ which is the standard notation for "coefficient of .. in ..." and helps to avoid confusions. $\endgroup$ – G Cab Dec 14 '17 at 22:44
  • $\begingroup$ You are right, thanks. $\endgroup$ – Fimpellizieri Dec 15 '17 at 1:40
1
$\begingroup$

As explained in the answer above, your process is equivalent to build all possible binary strings of length $n=m+s$ , with $m$ zeros = blue balls and $s$ ones = red balls.
Each different string is considered equi-probable.

Let me use the parameters $n,m,s$ defined as above (instead of your $n, n-k,k$) so as to keep congruency with the reference I am going to cite.

Now we want to count the strings having at least one run of $r$ consecutive ones and no longer than that.

This will include the strings in which the $r$ run occurs at the beginning and/or at the end of the string, in which case such runs will not be comprised between two zeros.
I will explain later how to account for only the runs comprised between two zeros, if that is what you need.

Then, as explained in my answer to this other post, the
number of binary strings, with $s$ ones and $m$ zeros, having at least one run of $r$ consecutive ones, and not longer
is given by $$N_b(s,r,m+1)-N_b(s,r-1,m+1)$$ where $$N_{\,b} (s,r,m+1) = \text{No}\text{. of solutions to}\;\left\{ \begin{gathered} 0 \leqslant \text{integer }x_{\,j} \leqslant r \hfill \\ x_{\,1} + x_{\,2} + \cdots + x_{\,m+1} = s \hfill \\ \end{gathered} \right.$$ which as explained in this other post is expressed as $$ N_b (s,r,m + 1)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s} {r}\, \leqslant \,m + 1} \right)} {\left( { - 1} \right)^k \left( \begin{gathered} m + 1 \\ k \\ \end{gathered} \right)\left( \begin{gathered} s + m - k\left( {r + 1} \right) \\ s - k\left( {r + 1} \right) \\ \end{gathered} \right)} $$ whose generating function in $s$ is $$ F_b (x,r,m + 1) = \sum\limits_{0\,\, \leqslant \,\,s\,\,\left( { \leqslant \,\,r\,\left( {m + 1} \right)} \right)} {N_b (s,r,m + 1)\;x^{\,s} } = \left( {\frac{{1 - x^{\,r + 1} }} {{1 - x}}} \right)^{m + 1} $$

If, instead, you want to count the strings in which the runs are only those comprised between two zeros, then take $2$ of the $m$ zeros and fix them to be at the beginning and at the end of the actual sub-string to be considered for counting the runs.
After that put $p$ ones at the beginning (before the zero), $q$ ones at the very end, and $s-p-q$ in the substring.
That means to count as above for the strings with $s-p-q$ ones and $m-2$ zeros, and sum over $p$ and $q$.

So, the

number of binary strings, with $s$ ones and $m$ zeros, having runs of consecutive ones with length up to $r$ , but counting only the runs comprised between two zeros

will be $$ \begin{gathered} N(s,r,m) = \sum\limits_{\left\{ \begin{subarray}{l} p,q \\ 0\, \leqslant \,p + q\, \leqslant \,s \end{subarray} \right.} {N_b (s - p - q,r,m - 1)} = \hfill \\ = \sum\limits_{\left\{ \begin{subarray}{l} p,q \\ \,p + q\, = \,t \end{subarray} \right.} {\sum\limits_{0\, \leqslant \,t\, \leqslant \,s} {N_b (s - t,r,m - 1)} } = \sum\limits_{\left\{ \begin{subarray}{l} p,q \\ \,p + q\, = \,s - t \end{subarray} \right.} {\sum\limits_{0\, \leqslant \,t\, \leqslant \,s} {N_b (t,r,m - 1)} } = \hfill \\ = \sum\limits_{0\, \leqslant \,t\, \leqslant \,s} {\left( {t + 1} \right)N_b (s - t,r,m - 1)} = \sum\limits_{0\, \leqslant \,t\, \leqslant \,s} {\left( {s - t + 1} \right)N_b (t,r,m - 1)} = \hfill \\ = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,t/r\, \leqslant \,m - 1} \right)} {\left( { - 1} \right)^k \left( \begin{gathered} m - 1 \\ k \\ \end{gathered} \right)\sum\limits_{0\, \leqslant \,t\, \leqslant \,s} {\left( {s - t + 1} \right)\left( \begin{gathered} t + m - 2 - k\left( {r + 1} \right) \\ t - k\left( {r + 1} \right) \\ \end{gathered} \right)} } = \hfill \\ = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,t/r\, \leqslant \,m - 1} \right)} {\left( { - 1} \right)^k \left( \begin{gathered} m - 1 \\ k \\ \end{gathered} \right)\sum\limits_{\left( {0\, \leqslant } \right)\,t\,\left( { \leqslant \,s} \right)} {\left( \begin{gathered} s - t + 1 \\ s - t \\ \end{gathered} \right)\left( \begin{gathered} t + m - 2 - k\left( {r + 1} \right) \\ t - k\left( {r + 1} \right) \\ \end{gathered} \right)} } = \hfill \\ = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,t/r\, \leqslant \,m - 1} \right)} {\left( { - 1} \right)^k \left( \begin{gathered} m - 1 \\ k \\ \end{gathered} \right)\left( \begin{gathered} s + m - k\left( {r + 1} \right) \\ s - k\left( {r + 1} \right) \\ \end{gathered} \right)} \hfill \\ \end{gathered} $$

Also, since we may write $N(s,r,m)$ as a double summation of $N_b(s,r,m-1)$ $$ \begin{gathered} N(s,r,m) = \sum\limits_{\left\{ \begin{subarray}{l} p,q \\ 0\, \leqslant \,p + q\, \leqslant \,s \end{subarray} \right.} {N_b (s - p - q,r,m - 1)} = \hfill \\ = \sum\limits_{0\, \leqslant \,s - p\, \leqslant \,s} {\sum\limits_{0\, \leqslant \,a\, \leqslant \,s - p} {N_b (a,r,m - 1)} } = \sum\limits_{0\, \leqslant \,b\, \leqslant \,s} {\sum\limits_{0\, \leqslant \,a\, \leqslant \,b} {N_b (a,r,m - 1)} } \hfill \\ \end{gathered} $$ then its generating function will be $$ G(x,r,m) = \sum\limits_{0\,\, \le \,\,s\,\,\left( { \le \,\,r\,\left( {m - 1} \right)} \right)} {N(s,r,m)\;x^{\,s} } = \frac{1}{{\left( {1 - x} \right)^2 }}\left( {\frac{{1 - x^{\,r + 1} }}{{1 - x}}} \right)^{m - 1} $$ confirming that given by Fimpellizieri.

Finally, the number of strings whose maximum run length is exactly $r$ will obviously be $N(s,r,m)-N(s,r-1,m)$.

$\endgroup$
  • $\begingroup$ This approach is similar to mine, and goes to emphasize how important generating functions are in a combinatorist's toolbox. That said, the constraint of considering only runs of $1$s that lie between $0$s is not trivial. $\endgroup$ – Fimpellizieri Dec 14 '17 at 18:50
  • $\begingroup$ @Fimpellizieri: you are totally right, it is not as trivial as I was putting that, and I amended the last part of my answer. My bad mistake, and thanks indeed for signalling it! $\endgroup$ – G Cab Dec 14 '17 at 23:39

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.