1. Subscribertalzamir
    Art, not a Toil
    60.13N / 25.01E
    Joined
    19 Sep '11
    Moves
    44224
    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.
  2. Joined
    28 Jul '07
    Moves
    97159
    01 Aug '13 21:14
    Originally posted by talzamir
    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.
    n
  3. Standard memberforkedknight
    Defend the Universe
    127.0.0.1
    Joined
    18 Dec '03
    Moves
    15977
    02 Aug '13 20:581 edit
    Originally posted by neilarini
    n
    It is just 1 - 1/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?"
  4. Subscribertalzamir
    Art, not a Toil
    60.13N / 25.01E
    Joined
    19 Sep '11
    Moves
    44224
    03 Aug '13 15:02
    Is it..?

    1 letter, 1 envelope: 1 out of 1. 100 % chance; not 1 - 1/1 = 0%
    2 of each: 1 out of 2. 50 % chance. = 1 - 1/2
    3 of each: 4 out of 6. 67 % chance. = 1 - 1/3
    4 of each: 14 out 24. about 58.3%, not 1 - 1/4 = 75%.
  5. Standard memberforkedknight
    Defend the Universe
    127.0.0.1
    Joined
    18 Dec '03
    Moves
    15977
    04 Aug '13 14:24
    For 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.
  6. Subscribertalzamir
    Art, not a Toil
    60.13N / 25.01E
    Joined
    19 Sep '11
    Moves
    44224
    20 Aug '13 20:44
    Consider 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.
Back to Top