Random Permutation Statistics - Expected Cycle Size of A Random Element

Expected Cycle Size of A Random Element

We select a random element q of a random permutation and ask about the expected size of the cycle that contains q. Here the function is equal to, because a cycle of length k contributes k elements that are on cycles of length k. Note that unlike the previous computations, we need to average out this parameter after we extract it from the generating function (divide by n). We have

$\frac{\partial}{\partial u} g(z, u) \Bigg|_{u=1} = \frac{1}{1-z} \sum_{k\ge 1} k^2 \frac{z^k}{k} = \frac{1}{1-z} \frac{z}{(1-z)^2} = \frac{z}{(1-z)^3}.$

Hence the expected length of the cycle that contains q is

$\frac{1}{n} \frac{z}{(1-z)^3} = \frac{1}{n} \frac{1}{2} n (n+1) = \frac{1}{2} (n+1).$

Read more about this topic: Random Permutation Statistics

Famous quotes containing the words expected, cycle, size, random and/or element:

“I don’t think I can be expected to take seriously any game which takes less than three days to reach its conclusion.”
—Tom Stoppard (b. 1937)

“Only mediocrities progress. An artist revolves in a cycle of masterpieces, the first of which is no less perfect than the last.”
—Oscar Wilde (1854–1900)

“For truly I tell you, if you have faith the size of a mustard seed, you will say to this mountain, ‘Move from here to there,’ and it will move; and nothing will be impossible for you.”
—Bible: New Testament, Matthew 17:20.

“And catch the gleaming of a random light,
That tells me that the ship I seek is passing, passing.”
—Paul Laurence Dunbar (1872–1906)

“Only the rare expands our minds, only as we shudder in the face of a new force do our feelings increase. Therefore the extraordinary is always the measure of all greatness. And the creative element always remains the value superior to all others and the mind superior to our minds.”
—Stefan Zweig (18811942)