MediumProbabilitypr-159

Expected Cycles in a Permutation

Problem

Expected number of cycles in a uniformly random permutation of n items:

E[cycles] = H_n = 1 + 1/2 + ... + 1/n.

The k-th item ends a cycle with probability 1 / k when items are processed by relative rank. Return 0.0 for n <= 0.

Hint

Count cycle leaders with indicators and linearity of expectation.

case 1

in: [1]

expected: 1

case 2

in: [2]

expected: 1.5

case 3

in: [4]

expected: 2.083333333333333

case 4

in: [10]

expected: 2.9289682539682538

Starter codePython

def expected_cycles(n):
    # Your code here
    pass

4 test cases · run your code against them in the editor