[2 days left] Whatâ€™s wrong with your cloud strategy? Learn why multicloud solutions matter with Nimble Storage.Register Now

x
Solved

# permutation mappings..

Posted on 2004-09-28
Medium Priority
791 Views
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
Question by:younoeme
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 22

Expert Comment

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

wytcom earned 600 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

ID: 12174171
The number of derangements of N elements is [N!/e]
0

LVL 7

Expert Comment

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

LVL 7

Expert Comment

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

Author Comment

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

ID: 12174746
0

LVL 7

Expert Comment

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

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

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

0

LVL 7

Expert Comment

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

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

## Featured Post

Question has a verified solution.

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

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â€¦
This is a research brief on the potential colonization of humans on Mars.
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â€¦
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201â€¦
###### Suggested Courses
Course of the Month14 days, 18 hours left to enroll