Solved

permutation mappings..

Posted on 2004-09-28
10
726 Views
Last Modified: 2008-02-26
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
Comment
Question by:younoeme
10 Comments
 
LVL 22

Expert Comment

by:grg99
ID: 12171048
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
 
LVL 7

Accepted Solution

by:
wytcom earned 150 total points
ID: 12172963
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
 
LVL 84

Expert Comment

by:ozo
ID: 12174171
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!

 
LVL 7

Expert Comment

by:wytcom
ID: 12174243
Limit as N -> large of (N-1)/N )^N = 1/e
0
 
LVL 7

Expert Comment

by:wytcom
ID: 12174251
Limit as N -> large of ( (N-1)/N )^N = 1/e
0
 

Author Comment

by:younoeme
ID: 12174613
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
 
LVL 84

Expert Comment

by:ozo
ID: 12174746
0
 
LVL 7

Expert Comment

by:wytcom
ID: 12174769
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
 

Expert Comment

by:meaculpa1113
ID: 12174857
isnt, (N!/e)/N! = e?

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

0
 
LVL 7

Expert Comment

by:wytcom
ID: 12180275
meaculpa1113: (N!/e)/N! = 1/e

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

Featured Post

Independent Software Vendors: 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!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

A Guide to the PMT, FV, IPMT and PPMT Functions In MS Excel we have the PMT, FV, IPMT and PPMT functions, which do a fantastic job for interest rate calculations.  But what if you don't have Excel ? This article is for programmers looking to re…
Have you ever thought of installing a power system that generates solar electricity to power your house? Some may say yes, while others may tell me no. But have you noticed that people around you are now considering installing such systems in their …
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

679 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question