Solved

permutation mappings..

Posted on 2004-09-28
10
734 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
[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
  • Learn & ask questions
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
Technology Partners: 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

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.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
A second problem of optics 12 138
Table function 6 60
Autosar OS Multicore Share Resources confusion ? 2 193
Pre-Linear Regression Tests 2 61
Complex Numbers are funny things.  Many people have a basic understanding of them, some a more advanced.  The confusion usually arises when that pesky i (or j for Electrical Engineers) appears and understanding the meaning of a square root of a nega…
Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! https://www.google.com/about/careers/students/guide-to-technical-development.html How to Know You are Making a Difference at EE In August, 2013, one …
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.
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…

739 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