Re: permutation mappings

From: Michael Amling (nospam_at_nospam.com)
Date: 09/29/04 

Date: Wed, 29 Sep 2004 02:33:27 GMT

David Eather wrote:
> Peter Pearson wrote:
>
>>duffman wrote:
>>
>>>Let PI be a permutation of the integers 0,1,2,3...2^(n-1)
>>>...
>>>... Show the somewhat unexpected result that over 60% of mappings
>>>will have at least one fixed point.

   That's not true. It fails when n=1, and the probability of at least
one fixed point is only 50%.

>>>
>>>any ideas?
>>
>>Is this a homework assignment?
>>
>>In a mathematical games column long ago, this problem was
>>presented in another form: what are the odds of winning a
>>game in which Alice and Bob shuffle decks of cards, then
>>reveal cards simultaneously. If ever two cards match, Alice
>>wins, but if they get through the decks without encountering
>>a match, Bob wins.
>>
>>There's a quick and erroneous analysis that gets the right
>>answer. The only correct derivation I've seen was not quick.
>>
>>- Peter Pearson
>
> They should get just one match

   I agree the expectation value of the number of matches must be 1.
Proof: If Alice selects a permutation of the cards uniformly at random,
then it doesn't matter what Bob does with his. He may as well leave them
in order. If Alice uses a Fisher-Yates shuffle, the probability of the
the first card she exchanges staying in place is exactly 1/n, which
becomes the probability of that card matching Bob's corresponding card.
Thus the contribution of that card to the expectation value must be 1/n.
But there's nothing special about that card. The contribution of each
card to the expectation value must be 1/n, hence the total expected
number of matches must be n*1/n. QED.

   If the expected number of matches is 1, then the lowest possible
probability of 0 matches is 0, and that could only happen if the
probability of having more than one match were 0, which happens only
when the decks each consists of a single card. When there are at least
two cards, the probability of at least one match must be less than 1.
That's an upper limit.

   For a two-card deck the probability of zero matches is 1/2.
   With more than two cards, the probability of zero matches must be
strictly less than 1/2, since the expectation value is 1 and there is a
nonzero probability of more than 2 matches.
   Offhand the best lower limit I can establish is >50% when more than 2
cards in the deck, so I guess the OP will have to do his own homework.

--Mike Amling

Relevant Pages

  • Re: The universe looks designed to me
    ... Just like shuffling a deck of cards and examining the resulting order. ... but you were *guaranteed* to get some result with exactly that probability. ... Or shuffle four decks of cards together and observe a result that had ...
    (talk.origins)
  • Re: what are the odds of....
    ... The probability Pof getting a straight flush with suited connectors ... is the probability that you hit one of four combinations of cards by the ...
    (rec.gambling.poker)
  • Re: what are the odds of....
    ... The probability Pof getting a straight flush with suited connectors ... is the probability that you hit one of four combinations of cards by the ...
    (rec.gambling.poker)
  • Re: Need Some Help From Mathematicians or Statisticians
    ... probability of obtaining a particular protein of length 100 is 1 in 20 ... Assume a 'card eating beastie' that likes red cards and a second 'card ... Also remove 10 of the rounded objects and replace ...
    (talk.origins)
  • Re: A card game probability
    ... and another shuffled deck with cards turned facedown. ... We want to find the probability of having at ... I'm guessing that "bar" signifies the ...
    (sci.math)