Question about the expected number of sampling until one item out of k is found

Question

)

I have k items (let's say balls) that all have a different color, but I do not know the color until I pick them. I would like to know how many balls I have to pick until I get one with a specific color.

My line of thought is as follows.

For one item, I will need 1 pick in expectation. For two items, I will need 1/2*1+1/2*2=1.5 picks in expectation. For three items, I will need 1/3*1+1/3*1/2*2+1/3*1/2*3 = 2 picks in expectation. For four items, I will need 1/4*1+3/4*1/3*2+3/4*2/3*1/2*3+3/4*2/3*1/2*4 = 2.5 picks in expectation.

My feeling is that the general formula is (1/k)(k(k+1)/2) = (1/k)*(k^2+k)/2 = (k+1)/2.

Do you think that this is correct? Is there maybe a common english name for this formula where I could read more about it (english is not my first language, sorry :-( )

Thank you!

Answer 1

The expected number of picks before a given ball is picked is equal to the average over all balls. This is

$$ \frac1k\sum_{j=1}^kj=\frac1k\frac{k(k+1)}2=\frac{k+1}2\;. $$

I don't know a name for this specific formula, but linearity of expectation is a keyword under which you might learn more about this sort of calculation.

Answer 2

Hint:

Think of the balls as if they are randomly placed in a line. After that you start picking from left to right. The specific ball can take place $1,2,\dots,k$ and every spot has equal probability to be possessed by that ball. What is its expected position?