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:

“Perhaps of all our untamed quadrupeds, the fox has obtained the widest and most familiar reputation.... His recent tracks still give variety to a winter’s walk. I tread in the steps of the fox that has gone before me by some hours, or which perhaps I have started, with such a tip-toe of expectation as if I were on the trail of the Spirit itself which resides in the wood, and expected soon to catch it in its lair.”
—Henry David Thoreau (1817–1862)

“The Buddha, the Godhead, resides quite as comfortably in the circuits of a digital computer or the gears of a cycle transmission as he does at the top of a mountain or in the petals of a flower.”
—Robert M. Pirsig (b. 1928)

“One writes of scars healed, a loose parallel to the pathology of the skin, but there is no such thing in the life of an individual. There are open wounds, shrunk sometimes to the size of a pin-prick but wounds still. The marks of suffering are more comparable to the loss of a finger, or the sight of an eye. We may not miss them, either, for one minute in a year, but if we should there is nothing to be done about it.”
—F. Scott Fitzgerald (1896–1940)

“Novels as dull as dishwater, with the grease of random sentiments floating on top.”
—Italo Calvino (1923–1985)

“Lisa Fremont: Surprise is the most important element of attack. And besides, you’re not up on your private eye literature. When they’re in trouble it’s always their girl Friday who gets them out of it.
L.B. Jeffries: Well, is she the girl who saves him from the clutches of the seductive show girls and the over passionate daughters of the rich?
Lisa Fremont: The same.
L.B. Jeffries: That’s the one, huh? But he never ends up marrying her, does he? That’s strange.”
—John Michael Hayes (b. 1919)