Expected number of partitions with a red ball?

Question

Say that we have $k$ red balls and $n-k$ blacks balls for $n$ balls total. Then, say we partition the balls into equal sized groups of size $m$. What is the expected number of groups with a red ball?

It seems clear that I should use linearity of expectation of some sort. I tried calculating the probability that any one group has at least one red ball, but I can't seem to get my equation to match my code simulation result.

Any help would be appreciated

Answer 1

Let $X_i$ be an indicator random variable $=1$ if the $i^{th}$ group has a red ball, and $=0$ otherwise.

Then $P[i^{th}$ group has a red ball] $= \left[1 - \dfrac{\binom{n-k}{m}}{\binom{n}{m}}\right]$
Now the expectation of an indicator r.v. is just the probability of the event it indicates, so $E[X_i] = \left[1 - \dfrac{\binom{n-k}{m}}{\binom{n}{m}}\right]$

By linearity of expectation we have expectation of sum = sum of expectations,
$E[\sum{(X_i)}] = \sum{E(X_i)} = \dfrac{n}{m}\left[1 - \dfrac{\binom{n-k}{m}}{\binom{n}{m}}\right]$

Answer 2

If I understand this correctly we take one of the ${n\choose k}$ arrangements of these balls in a line and partition into groups of size $m$ of consecutive balls starting at the left and then ask about the expected number of groups containing at least one red ball. Alternatively we may start the computation by asking of the expectation of the number of groups containing no red ball. We thus use a marked generating function as in

$$\left. \frac{\partial}{\partial u} (uB^m - B^m + (R+B)^m)^{n/m}\right|_{u=1}$$

and get

$$\left. \frac{n}{m} (uB^m - B^m + (R+B)^m)^{n/m-1} B^m\right|_{u=1} \\ = \left. \frac{n}{m} ((R+B)^m)^{n/m-1} B^m\right|_{u=1} \\ = \frac{n}{m} B^m (R+B)^{n-m}.$$

Extracting coefficients we find

$$\frac{n}{m} [R^k] [B^{n-k}] B^m (R+B)^{n-m} = \frac{n}{m} [R^k] [B^{n-k-m}] (R+B)^{n-m} = \frac{n}{m} {n-m\choose k}.$$

Now to count the groups with at least one red ball we subtract from the number of groups which is $n/m$ and the result becomes

$$\bbox[5px,border:2px solid #00A000]{ \frac{n}{m} \left(1 - {n\choose k}^{-1} {n-m\choose k}\right).}$$

This matches the answer that was first to appear.

We may also check this by enumeration as shown below.

with(combinat);

ENUM :=
proc(n, k, m)
option remember;
local src, d, grp, run, reds, gf;

    if n mod m <> 0 then return FAIL fi;

    gf := 0;

    src := [seq(R, idx=1..k), seq(B, idx=k+1..n)];

    for d in permute(src) do
        reds := 0;
        for grp from 0 to n/m-1 do
            run := d[1+grp*m..m+grp*m];

            if numboccur(run, R) > 0 then
                reds := reds + 1;
            fi;
        od;

        gf := gf + u^reds;
    od;

    gf;
end;

EXENUM := (n, k, m) ->
subs(u=1, diff(ENUM(n, k, m), u))/binomial(n,k);

EX := (n, k, m) -> n/m*(1 - binomial(n-m,k)/binomial(n,k));