If you take all the natural numbers 1,2,3,4,... and randomly shuffle them up, what is the probability that no number ends up in its original position.

Not a math genius like many poasters here
but this looks like fun.


If we take two numbers, 1,2 and shuffle, there is a 50% chance no # is in the same position.

With three #s it is (.67 * .5) 33.5%

With four numbers (.75 *.67 *.5) 25.1%

five (.8 * .75 * .67 * .5) 20.1%

Hopefully I haven't made an idiot of myself so far...

So, I would think that the answer would be we are approaching zero (if I have used the term correctly here).

Experimentally I get a convergence to 36.79... Here's how I see it

For n numbers, there is N! ways to organize them

1 way will have all of them in the right place

C(N,2) will have all of them in the right except 2

C(N,3)*2! will have all of them in the right place except 3, this is because we're choose 3 from N to swap. For the 1st swapped slot we have only 2 choices because we can't choose the right number. Then we have 1 slot for the 2nd number and the last is fixed.

C(N,4)*3! will have them all in the right place except for 4 numbers

And so forth. Well, this works for up to N=4 but then it breaks so I've missed something. I underestimate more and more as N increases.

A well-known matching problem.

http://en.wikipedia.org/wiki/Derangement

Yes, but what exactly is it that has probability 1/e?

There's no "natural" method of choosing a "random" permutation of the
positive integers, so the 1/e is just a limit of probabilities for permutations
of finite sets which doesn't apply for permutations of countably infinite sets.

For any finite set that is arbitrarily large with n elements, the number of derangements is [n!*(1/e)] and the probability that no number ends up in its original position is 1/e.

For example, the probability that #1 is not in its original position is (n-1)/n

The probability that none of the n numbers is in its original position is

[(n-1)/n]^n = (1 - 1/n)^n = e^(-1)

We can recall that the definition of e^x is the limit as n approaches infinity of (1+x/n)^n

Exactly! You got it completely! The limit (as n goes to infinity) of the probabilities (for a permutation of n elements to be a derangement) exists and is 1/e, but it seems that the limit of the corresponding probability distributions is not well defined.

I wonder if this has some connection to the topic of `amenable groups'.

http://en.wikipedia.org/wiki/Amenable_group

Anyway it's fair to say that the "probability" of a "random" permutation of and infinite set being a derangement "should" be 1/e. It's just so tempting to say that. So I wonder to what extent this can be set up in a well defined way in the infinite case.

Sorry if this thread seems out of place amongst the "what is the probability of getting two heads in a row' threads.

Sure, that would be "nice". It seems like there could be a connection with
discrete amenable groups, but you would have to consult a researcher in
this field to get an idea of what type of "nice theorems" work with what kind
of discrete groups ( and it seems that the countable case could have been
analyzed already ). I wonder if it is true that for all p in (0,1) ( forget 0 and
1 for now ), there exists some "way" to choose a random bijection ( that
resembles the "equally weighted" means for finite permutations ) of the set
N of natural numbers onto itself such that the "probability" of no fixed point
is p. Of course, there "should be" many "ways" where this "probability" is 1/e
and it could be that for "almost every reasonable way" this "probability" is 1/e.
Also, it could even be wrong to think that "infinite permutations" should
behave like finite permutations. [ I put probability in quotes, because there
may not be a nice way to define such a measure on the set of permutations. ]

It's refreshing to have "open problems" rather than the usual common
questions that could be answered by "googling".