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$

Improve this question
$\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
    Commented May 25, 2013 at 13:34

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .