Expected number of runs in a random permutation

Posted on March 28, 2014 by phimuemue

My last post was about the expected number of cycles in a random permutation. Today, we'll compute the expected number of runs in a random permutation.

Runs in permutations

First of all, we'll consider what we even mean when we talk about runs in a permutation. If we have a certain permutation, say \(2, 6, 3, 1, 7, 9, 4, 5, 8, 10\), i.e. simply written as a sequence of numbers. We can now decompose this sequence of numbers into smaller subsequences such that each subsequence is strictly increasing, thereby, we obtain the following subsequences: \([2,6],[3],[1,7,9],[4,5,8,10]\).

First elements of runs

Now, to compute the expected number of runs if we pick one permutation of the numbers \(\{1,2,3,\dots,n\}\) at random, we can do the following: We do not actually focus on the runs itself, but instead just on the beginning of each run.

The first position in a permutation automatically marks the beginning of a run (namely the beginning of the first run).

Let us now think about whether the second position marks the beginning of a new run. In fact, the second position marks the beginning of a new run with a probability of exactly \(0.5\). This is clear because there can be two cases:

It is clear that both of the above events occur with probability \(0.5\) because for each situation where the second number is greater than the first, we can acchieve the other situation by swapping the first and second element in the permutation.

The same reasoning works for the remaining positions \(3,4,\dots,n\), so that we know that the probability that a new run starts at position \(i\geq 2\), is given by \(0.5\) regardless of the particular value of \(i\).

Expected number of runs

We can now compute the expected number of runs by installing some indicator variables: The variable \(I_i\) (for \(i\geq 2\)) is 1 if the element at position \(i\) marks the beginning of a run, otherwise 0.

We can then compute the number of runs by \(1+\sum_{i=2}^n I_i\) (the constant 1 comes from the fact that the first position always marks the beginning of a run).

So, we obtain that the expected number of runs is (using linearity of expectation) given by \(E[1+\sum_{i=2}^n I_i] = 1 + \sum_{i=2}^n E[I_i] = 1 + \sum_{i=2}^n Pr[I_i = 0] = 1 + \sum_{i=2}^n 0.5 = \frac{n+1}{2}\).

Testing

The following method computes the runs in a permutation:

def runs(p):
    if len(p)==0:
        return []
    r = [[p[0]]]
    for x in p[1:]:
        if x > r[-1][-1]:
            r[-1].append(x)
        else:
            r.append([x])
    return r

We can verify our results by running:

for i in xrange(1,10):
    a = list(range(i))
    s = 0
    for p in itertools.permutations(a):
        s = s + len(runs(p))
    avg = Fraction(s, factorial(i))
    print "%d : %f"%(i, avg)