0

Suppose there are $500$ people in our office. I want to find the probability of drawing my friend's name. Rules: every person picks out a name from a hat without replacement and for this problem, it's fine to draw one's own name if that simplifies calculation. (Alternatively, calculation may be simpler if we disallow picking one's own name - that's fair game too - whatever makes our life easier)

My approach is to model the probability of being the $k$-th person to draw, or $Q_k$, and the probability of the $k$-th person drawing my friend's name, or $P_k$, via a recurrence relation: $$P_k = (1-P_1)(1-P_2)\ldots (1-P_{k-1})\bigg(\frac{1}{500-k}\bigg)$$

$$Q_k=(1-Q_1)(1-Q_2)\ldots(1-Q_{k-1})\bigg(\frac{1}{500-k+1}\bigg)$$

Then the answer can be expressed as $\sum P_k Q_k$.

But this doesn't seem to result in a nice answer. Is there something I'm missing in this method? Is there an alternative method instead?

Shirish Kulhari
  • 2,529
  • 5
    It is not clear to me what you are after. Is one of the names the name of your friend and are you drawing a name? Then - if there are $n$ names and only one of them is the name of your friend - the probability that this happens if $\frac1n$. – drhab Dec 21 '18 at 12:45
  • The equation for $P$ should match the one for $Q$, otherwise you end up with division by zero when $k=500$. – David Diaz Dec 21 '18 at 18:17
  • You seem to think the ;probability depends on when you get to pick. It doesn't so it's $1/500$, See: https://math.stackexchange.com/questions/1875045/is-this-lot-drawing-fair/1875055#1875055 – Ethan Bolker Dec 21 '18 at 18:32

1 Answers1

1

It does result in a nice answer. Suppose you have $n$ people in your office.

$$Q_k = \frac{1}{n}$$ $$P_k = \frac{1}{n}$$ $$\sum_{k=1}^nQ_kP_k = \sum_1^n\frac{1}{n^2} = \frac{n}{n^2} = \frac{1}{n}$$

So why is $Q_k = (1-Q_1)(1-Q_2)\dots(\frac{1}{n-k+1}) = \frac{1}{n}$?

$Q_1 = \frac1{n}$

$Q_2 = \frac{n-1}{n}\frac{1}{n-1}$

$Q_3 = \frac{n-1}{n}\frac{n-2}{n-1}\frac{1}{n-2}$

etc.

If you need a proof, induction would work nicely here.

David Diaz
  • 2,218