Question

Randomized Leader Election

A group of n people sit together and each one chooses a uniformly random integer in {1,…,n} independent of the others choices, we have a sequence (x1,…,xn)∈{1,…,n}n. Each person, i, announces their number ni, and all people compute m=max{ni:i∈{1,…,n}}. The algorithm succeeds if there is exactly one i∈{1,…,n} such that ni=m. (In this case, person i is declared the leader.)

Define pn as the probability that this algorithm succeeds with a group of n people.

1. Compute p2
2. Compute p3
3. Derive a formula for pn that is valid for any integer n≥1.

Answer 1