0
$\begingroup$

I was asked this question during my interview recently and despite the amount of thinking i put into this, I am yet to figure it out:


Given $n$ balls which are painted by $k$ colors. Let $s_i$ number of balls painted color $i$, $\sum(s_i)=n$. If we go from left to right, what is the expected number of color change?

Example: for ($n$=8, $k$=3), this configuration $(1,1,1,2,2,2,3,3)$ has $2$ color changes. (previously I typed $3$ instead of $2$). Another configuration, $(1,2,3,1,3,2,2,1)$ has 6

Updated: It was $2$ instead of $3$

$\endgroup$
1
  • 2
    $\begingroup$ Your "changes" should be "groups", if you want the answer 3 rather than 2 in your example, though the counts always just differ by 1. Hint: the expectation of the sum is the sum of the expectations no matter what, so just look at each adjacent pair of balls separately (they are all the same, really). Another hint: use AoPS rather than MO for discussions of such problems. Voting to close. $\endgroup$
    – fedja
    May 25, 2013 at 13:34

1 Answer 1

2
$\begingroup$

Use the method of indicator variables and the linearity of expectation. For each $i$ in $\lbrace 1,\dots,n-1\rbrace$, the probability that the $i$-th and $(i+1)$-st balls have the same color is $[s_1(s_1-1)+\dots+s_k(s_k-1)]/n(n-1)$. Subtract from $1$, multiply by $n-1$, and simplify. The final answer is $n-(s_1^2+\dots+s_k^2)/n$.

$\endgroup$

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