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:

“There were ghosts that returned to earth to hear his phrases,
As he sat there reading, aloud, the great blue tabulae.
They were those from the wilderness of stars that had expected more.
There were those that returned to hear him read from the poem of life,
Of the pans above the stove, the pots on the table, the tulips among them.
They were those that would have wept to step barefoot into reality....”
—Wallace Stevens (1879–1955)

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

“Delusions that shrink to the size of a woman’s glove,
Then sicken inclusively outwards:
. . . the incessant recital
Intoned by reality, larded with technical terms,
Each one double-yolked with meaning and meaning’s rebuttal:
For the skirl of that bulletin unpicks the world like a knot....”
—Philip Larkin (1922–1986)

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

“There is probably an element of malice in the readiness to overestimate people: we are laying up for ourselves the pleasure of later cutting them down to size.”
—Eric Hoffer (1902–1983)