[Enunciado] Queremos provar que E[X] = ∑0 ≤ i ≤ n i Pr[X = i].
PROVA: Seja Π o conjunto de todas as permutações de 1 .. n. Para cada A em Π, seja N(A) o número de execuções da linha 4 quando Máximo processa A[1 .. n]. Então E[X] = ∑ (N(A) : A ∈ Π) / n!. Como 0 ≤ N(A) ≤ n, podemos reorganizar a soma assim:
E[X] = ∑ (i M(i)/n! : 0 ≤ i ≤ n),
sendo M(i) = ⎮{ A ∈ Π : N(A) = i }⎮. Mas M(i)/n! = Pr[X = i], CQD.