Saturday, December 27, 2008

Combinatorics Question

Suppose we are sampling permutations of the first N positive integers from a uniform distribution. For any two integers x and y, what is the probability that they lie in same cycle?

For example, suppose we sampled the following permutation using the first 5 positive integers:

2 3 1 5 4

Then {1,2,3} form a cycle because position 1 points to 2, position 2 points to 3, and position 3 points to 1. Likewise {4,5} also form a cycle.

2 comments:

Lev said...

Awesome problem. I spent some time making recurrences that I couldn't solve, and then I noticed the symmetry. Answer = 1/2.

Yisong said...

Yeah, it's quite nice. I came across the problem watching one of Michael Jordan's lecture videos.

In his talk, he associates it to the probability that, in the Chinese Restaurant Process, the first two guests sit at the same table.