MathDB

expected value of random variable X is \sum_{k=1}^n \frac{1}{k!}

Source: Polish MO Recond Round 1989 p2

September 9, 2024

probabilitycombinatoricspermutation

Problem Statement

For a randomly selected permutation

\mathbf{f} = (f_1,..., f_n)

of the set

\{1,\ldots, n\}

let us denote by

X(\mathbf{f})

the largest number

k \leq n

such that

f_i < f_{ i+1}

for all numbers

i < k

. Prove that the expected value of the random variable

X

\sum_{k=1}^n \frac{1}{k!}