• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 808
  • Last Modified:

permutation mappings..

Let PI be a permutation of the integers 0,1,2,3...2^(n-1), such that
PI(m) gives the permuted value of m, 0 <= m < 2^n.  Put another way,
PI maps the set of n-bit integers into itself and no two integers map
into the same integer.  DES (Data Encryption Standard, for those who
don't know a really popular way of encrypting data in a block-cipher
fashion) is such a permutation for 64 bit integers.  We say that PI
has a fixed point at m if PI (m) = m. That is, if PI is an encryption
mapping, then a fixed point comes points to a message that encrypts to
itself.  We are interested in the probability that PI has no fixed
points.  Show the somewhat unexpected result that over 60% of mappings
will have at least one fixed point.

pretty interesting..
0
younoeme
Asked:
younoeme
1 Solution
 
grg99Commented:
This sounds a lot like the old chestnut, the "same birthday" problem, only without the attractive waitress.

You basically have to add the probablity that m will not map to m, for all m in the range 2^n.

So it's something like    (1/(2^n - 1) )   ^  (2^n)   ?

0
 
wytcomCommented:
Think of N people sitting in N chairs.  Now we have them all get up and randomly select them as we refill the seats in order.  What is the probability that nobody gets their original seat back?  

1st person:
  Prob that seat is not occupied yet = 1
  Prob of missing original seat = (N-1)/N

2nd person:
  Prob that seat is not occupied yet = (N-1)/N
  Prob of missing original seat = (N-2)/(N-1)

nth person:
  Prob that seat is not occupied yet = (N-n)/N
  Prob of missing original seat = (N-n)/(N-n+1)

To get the probability that nobody through the nth person has yet been seated in their original seat we require that the 1st person was not and the 2nd and ...
The probability that the nth person was not seated in his original seat is the probability that it was unoccupied and he was not seated in it or that it was already occupied:
  (N-n)/N + (n-1)/N

So to get the probability that all persons were seated in a different seat from their original:
  Product for n=1 to N of [ (N-n)/N + (n-1)/N ]  
 =  Product for n=1 to N of [ (N-1)/N ]
 = ( (N-1)/N )^N

Subtract this from 1 to get the probability that at least one person was seated in their original seat:
  1 - ( (N-1)/N )^N

For N = 2^m

m            1 - ( (N-1)/N )^N

8      63.28%
12      63.22%
16      63.21%
20      63.21%
24      63.21%
28      63.21%
0
 
ozoCommented:
The number of derangements of N elements is [N!/e]
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
wytcomCommented:
Limit as N -> large of (N-1)/N )^N = 1/e
0
 
wytcomCommented:
Limit as N -> large of ( (N-1)/N )^N = 1/e
0
 
younoemeAuthor Commented:
i appreciate and fully understand the answer that  wytcom has posted above..

wat does ozo mean by the number of derangements of N elements is N!/e?


0
 
wytcomCommented:
I think ozo is giving us a known result that covers this situation.

deraangement = unique arrangement without any fixed points.

So the number of ways to redistribute the set of integers without any fixed points would be N!/e (where e is the natural number = 2.718).

Using this, the probability that a random arangement has no fixed points is
1 - (N!/e)/N!      
since there are N! total arrangments and N!/e derangements.

My analysis can be regarded as a derivation of the rule that ozo stated.
0
 
meaculpa1113Commented:
isnt, (N!/e)/N! = e?

in which case it is, 1 - e..?

0
 
wytcomCommented:
meaculpa1113: (N!/e)/N! = 1/e

(x/e)/x = x/(e*x) = 1/e
0

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now