Solved

permutation mappings..

Posted on 2004-09-28
10
654 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
 
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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 

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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Baseline sigma 8 29
Roulette strategy probability question 58 90
Probability Distribution 5 43
coolers to wear for eyes in workplace (8-10 hours of computer starring!) 10 99
Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethi…
Article by: Nicole
This is a research brief on the potential colonization of humans on Mars.
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
This is a video that shows how the OnPage alerts system integrates into ConnectWise, how a trigger is set, how a page is sent via the trigger, and how the SENT, DELIVERED, READ & REPLIED receipts get entered into the internal tab of the ConnectWise …

932 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

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now