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:

“[My father] was a lazy man. It was the days of independent incomes, and if you had an independent income you didn’t work. You weren’t expected to. I strongly suspect that my father would not have been particularly good at working anyway. He left our house in Torquay every morning and went to his club. He returned, in a cab, for lunch, and in the afternoon went back to the club, played whist all afternoon, and returned to the house in time to dress for dinner.”
—Agatha Christie (1891–1976)

“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)

“It is very considerably smaller than Australia and British Somaliland put together. As things stand at present there is nothing much the Texans can do about this, and ... they are inclined to shy away from the subject in ordinary conversation, muttering defensively about the size of oranges.”
—Alex Atkinson, British humor writer. repr. In Present Laughter, ed. Alan Coren (1982)

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

“The element running through entire nature, which we popularly call Fate, is known to us as limitation. Whatever limits us, we call Fate.”
—Ralph Waldo Emerson (1803–1882)