2

I came across this problem from a probability practice book. Could someone give me a hint?

Suppose you have N balls and M of them are red(others aren't red). You keep picking one ball out and NOT putting it back until you get one red ball. Find the expectation of a number of balls you need to pick out.

My approach is to use recursion. Let $X_k$ denote the distribution of number of balls I need to pick to get a red ball with k balls in the pool. Then,

$E(X_k)=\frac{M}{k} + \frac{k-M}{k}(1+E(X_{k-1}))$ , with $E(X_M) = 1$

as with M ball left in the pool, it should be immediate to pick a red ball. But then I end up an equation that I couldn't solve.

$E(X_N) = 1+\frac{N-M}{N}(1+\frac{N-1-M}{N-1}(1+...(1+\frac{1}{M+1}(1+1))))$

can anyone give me a hint or guide me please?

JMP
  • 21,771
junyaozheng98
  • 81

2 Answers2

1

Let $\tau$ be the number of balls drawn until the first red ball is drawn. Then for $1\leqslant n\leqslant N-M+1$ we have $$ \mathbb P(\tau = n) = \frac M{N-(n-1)}\prod_{i=1}^{n-1}\frac{N-M-(i-1)}{N-(i-1)} $$ So the expected number of balls drawn is $$ \mathbb E[\tau] = \sum_{n=1}^{M-n+1} n\cdot\mathbb P(\tau = n) = \sum_{n=1}^{N-M+1}\frac M{N-(n-1)}\prod_{i=1}^{n-1}\frac{N-M-(i-1)}{N-(i-1)}. $$ It turns out this expression has the closed form $$ 1 + \frac{N}{M+1}, $$ as explained in this answer: Expected Value Of Number of Removals From Urn

Math1000
  • 36,983
0

I liked your approach of searching for a recurrence relationship! Its definitely something I would have tried!

Let us think of a slightly different game which you should be able to see is identical to your one.

Let us get $N$ black cards and $M$ red cards. Lets shuffle these well. Notice that your problem is the same as the expected number of cards we must pick of the top until a red card appears.

Let us think of a way to answer that question. Firstly we can add a joker aswell that will be seen as a start position. We can consider the red and joker as "special cards" and the black cards as standard.

Now notice in a well shuffled deck we have $M+1$ special cards, the $M$ red and $1$ joker and $N$ standard cards. Hence we have a total of $N+M+1$ cards. Hence the expected difference between consecutive special cards is $\frac{N+M+1}{M+1}$

So lets draw cards like this. We consider the joker as the "top of the deck" so we shuffle the cards then locate the joker and start drawing from there. We already saw that the expected difference between consecutive special cards, i.e the joker and the first red card is $\frac{N+M+1}{M+1}$ so this is our answer.

$\frac{N+M+1}{M+1} = 1 + \frac{N}{M+1}$ if you wanted it in a more concise way

Quick notice that all this joker shinanigans does nothing to change the "randomness" or fairness. It is a perfectly valid way of dealing cards randomly. Try it out.