Quote:
Originally Posted by thylacine
Quote:
Originally Posted by thylacine
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.
My first reaction is that this is not a well-posed problem, since a probability distribution on permutations of naturals was not specified. If we were shuffling a finite set {1,...,N}, I would consider the problem well-posed, with the implied distribution being uniform. Given that, I think the best answer is the obvious one, given in the main thread: 1/e, which is the limit of the answer to the finite question as N → ∞. I am skeptical about the possibility of creating a distribution directly on permutations of the naturals which captures this idea.
A natural extension of uniform permutations of {1,...,N} to the infinite case is a random ordering (which is not a permutation). Let X
1, X
2, ... be iid random variables with continuous distribution. Then {X
1, ..., X
N} induces a uniform permutation
σ on {1, ..., N} via X
σ(1) < ... < X
σ(N). In the limit, the entire sequence X
1, X
2, ... induces a random linear ordering on the naturals given by i < j iff X
i < X
j. Of course, this does not help much with the original question, since we lose the concept of fixed points. But it is a pretty natural probabilistic construction, so it may be worth considering.