Solved

permutation mappings..

Posted on 2004-09-28
10
648 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
Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

 

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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

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 …
We are taking giant steps in technological advances in the field of wireless telephony. At just 10 years since the advent of smartphones, it is crucial to examine the benefits and disadvantages that have been report to us.
Get a first impression of how PRTG looks and learn how it works.   This video is a short introduction to PRTG, as an initial overview or as a quick start for new PRTG users.
Here's a very brief overview of the methods PRTG Network Monitor (https://www.paessler.com/prtg) offers for monitoring bandwidth, to help you decide which methods you´d like to investigate in more detail.  The methods are covered in more detail in o…

746 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

11 Experts available now in Live!

Get 1:1 Help Now