Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$

share|improve this question
2  
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. –  fedja May 25 '13 at 13:34
add comment

closed as off topic by fedja, Gjergji Zaimi, Douglas Zare, Benoît Kloeckner, Tony Huynh May 25 '13 at 23:11

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer

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$.

share|improve this answer
add comment

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