Expected number of local maxima

Background

The problem statement is:

Given a random \(N>=2\), find the expected number of local maxima for a random permutation of numbers \(1, 2, ..., N\) (given that each permutation is equally likely). For example, given a permutation 1, 4, 2, 3 - there are 2 local maxima (4 and 3).

Problem statement

This is a very hard problem and professor gives a simple solution. When I discussed this with my friend, we thought of another, but similar problem:

What is expected nubmer of local maxima in a list of \(N\) numbers where every number can take values \(1, 2, ..., N\) with equal probability.

I wanted to see whether similar simple logic could be applied.

SPOILER ALERT

Solution

Let \(M_j\) be an indicator r.v. that equals 1 if \(A[j]\) is a local maxima. Then the answer is \(E[M_1 + M_2 + ... + M_N] = E[M_1] + E[M_2] + ... + E[M_N]\). By simmetry, \(E[M_1] = E[M_N]\), so let \(E[M_1] = Border\), and let \(E[M_2] = E[M_3] = ... = E[M_{N-1}] = Middle\).

The answer is then: \(2Border + (N - 2)Middle \).

Looking at any middle element and its neighbors, there are \(N^3\) possible triples. Out of these, only the following cases make the middle element be the local maxima:

• \(left=a, middle=b, right=c, b>a, b>c, a \neq c\)
• \(left=a, middle=b, right=a\)

In all other cases the middle element is not a local maxima. There are \(N(N-1)(N-2)\) ways to choose \(3\) distinct numbers out of \(N\). Only \(1/3\) of these are such that b is the maximum. There are \(N(N-1)\) ways to choose \(2\) distinct numbers out of \(N\). Only \(1/2\) of these are such that b is the maximum. So, for any middle element \(E[M_j] = Middle = \frac{N(N-1)(N-2)/3 + N(N-1)/3}{N^3} = \frac{(N-1)(N-2)/3 + (N-1)/2}{N^2}\).

Looking at any border element, there are \(N^2\) possible pairs. Out of these, only \(N(N-1)\) are pairs where numbers are distinct, and only \(1/2\) of these have the first number bigger than the second. So \(E[M_1]=E[M_N]= Border = \frac{N(N-1)/2}{N^2} = \frac{(N-1)/2}{N}\).

The final answer then is \(\frac{N - 1}{N} + (N - 2)\frac{(N-1)(N-2)/3 + (N-1)/2}{N^2}\).

An interesting observation can be made. \(\lim_{N \to \infty}\Bigl(\frac{N - 1}{N} + (N - 2)\frac{(N-1)(N-2)/3 + (N-1)/2}{N^2}\Bigr) = 1 + \frac{N-2}{3}\), which is exactly the same as the expected number of local maxima for a random permutation of numbers \(1, 2, ..., N\) - what a surprise!

Experimental part

Runtime complexity of the naive approach below is \(O(N^{N+1})\) - since it takes \(O(N)\) to verify each of \(N^N\) arrangements - which means we could hope to verify maybe up to \(N=10\).

Below is a sample program.

def local_maxima(v):
    """Returns the number of local maxima in a given list.

    Elements in the list must not be negative.

    For example, for v=[1, 4, 2, 3] it returns 2."""
    q = [-1] + v + [-1]
    res = 0
    for i, val in enumerate(q):
        if val < 0:
            continue
        if val > q[i - 1] and val > q[i + 1]:
            res += 1

    return res


def gen_next(v, n):
    """Mutates v so it contains next arrangement or [].

    For example, n=3 and v=[0,1,2]. Then v will be set to [0,2,0].
    If n=3 and v=[2, 2, ], then v will be set to [].
    """
    pnt = len(v) - 1
    carry = 1
    while pnt >= 0:
        v[pnt] += carry
        carry = v[pnt] // n
        v[pnt] = v[pnt] % n
        pnt -= 1

    if carry > 0:
        v[:] = []
    return v


def exp_local_maxima_formula(n):
    r1 = n * (n - 1) / (n * n)
    r2 = (n - 2) * (n - 1) * (n - 2) / 3.0
    r3 = (n - 2) * (n - 1) / 2.0
    return r1 + (r2 + r3) / (n * n)


def exp_local_maxima_brute(n):
    v = [0] * n
    trials = 0
    local_maximas = 0
    while len(v) > 0:
        local_maximas += local_maxima(v)
        trials += 1
        gen_next(v, n)
    return 1.0 * local_maximas / trials


if __name__ == "__main__":
    assert local_maxima([1, 2, 1]) == 1
    assert local_maxima([1, 1, 1]) == 0
    assert local_maxima([1, 4, 2, 3]) == 2

    assert gen_next([0], 2) == [1]
    assert gen_next([1], 2) == []
    assert gen_next([0, 0], 2) == [0, 1]
    assert gen_next([0, 1], 2) == [1, 0]
    assert gen_next([1, 0], 2) == [1, 1]
    assert gen_next([1, 1], 2) == []

    for n in range(2, 9):
        b = exp_local_maxima_brute(n)
        f = exp_local_maxima_formula(n)
        e = abs(b - f)
        print('n={}\tbrute-force={:.2f}\tformula={:.2f}\terror={:.2f}'.format(n, b, f, e))

$ python3 main.py
n=2	brute-force=0.50	formula=0.50	error=0.00
n=3	brute-force=0.85	formula=0.85	error=0.00
n=4	brute-force=1.19	formula=1.19	error=0.00
n=5	brute-force=1.52	formula=1.52	error=0.00
n=6	brute-force=1.85	formula=1.85	error=0.00
n=7	brute-force=2.18	formula=2.18	error=0.00
n=8	brute-force=2.52	formula=2.52	error=0.00

Back to main page

© Copyright 2020, Iaroslav Tymchenko