01 Aug '13 09:38

I have n letters and n envelopes. If I put the letters in the envelopes randomly, one in each, find the probability that at least one letter is in the right envelope.

- Joined
- 19 Sep '11
- Moves
- 46536

60.13N / 25.01E- Joined
- 28 Jul '07
- Moves
- 103725

- Joined
- 18 Dec '03
- Moves
- 16652

127.0.0.102 Aug '13 20:581 edit

It is just 1 - 1/n.*Originally posted by neilarini***n**

The series of probabilities that all letters will be in the wrong envelop is:

P = (n-1)/n * (n-2)/(n-1) * ... * 2/3 * 1/2

which reduces to

P = (n - 1)! / n! = 1/n

The probably of any given letter being in the correct envelop is the inverse:

~P = 1 - P

~P = 1 - 1/n

This is actually the same odds you get for card games like poker: "If I draw n cards, and I need to draw any one of X cards to win, what are my chances of winning?"- Joined
- 19 Sep '11
- Moves
- 46536

60.13N / 25.01E- Joined
- 18 Dec '03
- Moves
- 16652

127.0.0.104 Aug '13 14:24For 1 envelop, (n-1)! / n! doesn't quite simplify to 1/n, you're right.

P = (n-1)! / n! = 0/1

~P = 1 - 0/1 = 1

I'm trying to figure why it doesn't work for n > 3. I think because I'm double-counting certain cases like:

n = 4

3/4 chance of not drawing 1: draw 3

2/3 chance of not drawing 2: draw 4

Now there are no possible ways to match any envelope.- Joined
- 19 Sep '11
- Moves
- 46536

60.13N / 25.01E20 Aug '13 20:44Consider this as all the possible permutations of n numbers. Letter to the right envelope then matches the case of some number k is at the k'th place.

n = 1: only sequence is 1. 1 / 1! = 1, so 100% chance.

n = 2: new sequences can be generated by replacing any number in any above sequence with a 2, and moving the replaced number to the end of the sequence. If it was formerly in the right place, this reduces the # of letters to the right place by one; if not, it the number of letters to the right place stays the same. OR, for any sequence above, 2 can be added to the end, increasing the # of letters to the right place by one.

Replace: 1 --> 21. reduces the # of hits to zero. "zero hits, two misses." (0,2)

Add to the end: 1 --> 12. adds the # of hits to two. "zero misses, two hits." (2,0)

n = 3:

(0,2) sequence; replace either with a three for 2x(0,3) or add 3 to the end (1,2).

(2,0) sequence; replace either with a three for 2x(1,2) or add 3 t the end (3,0)

(0,3) x2

(1,2) x3

(3,0) x1 four involve hits. 4/3! = 67%

n = 4:

(0,3)x2: replace any for 6x(0,4) or add 4 to the for 2x(1,3)

(1,2)x3: replace the only hit for 3x(0,4), replace either miss for 6x(1,3) or add the end for 3x(2,2)

(3,0): replace any hit for 3x(2,2) or add 4 to the end for (4,0).

Which yields

(0,4) x9

(1,3) x8

(2,2) x6

(4,0) x1 all but 9 include at least one hit, so 15/4! gives the likelihood.

And so on and and so forth. There is a non-trivial limit for the chance of at least one hit as n grows without limit, and the sequences approaches that value fast. Sadly, so far I haven't figured out a pretty way to get the likelihood for k envelopes in a pretty, closed form.