Saturday, February 20, 2010

Another Fun Math Problem

Assume we have a set S of n distinct integers and a permutation Q of S drawn uniformly from the set of a possible permutations. We wish to analyze a procedure that maintains a current largest seen value C as it iterates through the permutation of S. Initially, C is set to be negative infinity (or some practical equivalent thereof). Our procedure then iterates through the elements of S in the order defined by Q. Whenever we encounter a number larger than C, we update C to be this newly seen largest value so far. How many updates should we expect to observe from running this procedure?

2 comments:

Derek said...

Expected number of updates = $H_n$, where $H$ is the harmonic series?

Yisong said...

That is correct =)