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:

“What strikes me as odd now is how much my father managed to get across to me without those heart-to-hearts which I’ve read about fathers and sons having in the study or in the rowboat or in the car.... Somehow I understood completely how he expected me to behave, in small matters as well as large, even though I can’t remember being given any lectures about it beyond the occasional, undramatic “You might as well be a mensch.””
—Calvin Trillin (20th century)

“The cycle of the machine is now coming to an end. Man has learned much in the hard discipline and the shrewd, unflinching grasp of practical possibilities that the machine has provided in the last three centuries: but we can no more continue to live in the world of the machine than we could live successfully on the barren surface of the moon.”
—Lewis Mumford (1895–1990)

“Our brains are no longer conditioned for reverence and awe. We cannot imagine a Second Coming that would not be cut down to size by the televised evening news, or a Last Judgment not subject to pages of holier-than-Thou second- guessing in The New York Review of Books.”
—John Updike (b. 1932)

“Assemble, first, all casual bits and scraps
That may shake down into a world perhaps;
People this world, by chance created so,
With random persons whom you do not know—”
—Robert Graves (1895–1985)

“To get a man soundly saved it is not enough to put on him a pair of new breeches, to give him regular work, or even to give him a University education. These things are all outside a man, and if the inside remains unchanged you have wasted your labour. You must in some way or other graft upon the man’s nature a new nature, which has in it the element of the Divine.”
—William Booth (1829–1912)