So here’s a problem from the Putnam exam (http://en.wikipedia.org/wiki/Putnam_exam), one of the hardest math exams in the country. This problem was discussed in stat 110. It has a solution which is not hard to understand but is difficult to come up with on your own.

The Problem:

Given a random permutation of integers 1, 2, 3, …, n with a discrete, uniform distribution, find the expected number of local maxima. (A number is a local maxima if it is greater than the number before and after it.) For example, if n=4 and our permutation was 1, 4, 2, 3, then the # of local maxima would be 2 (both 4 and 3 are maxima).

Solution:

At first glance, this seems like a very difficult problem to solve. It involves a random permutation on a set of integers of variable length.

The key is using indicator variables. (For anyone who took stat 110, you’ll remember that the professor loved this trick, and it is in fact very useful for many difficult problems.)

We’ll make an indicator variable IND(j) where IND(j) is 1 if the j-th number is a local maxima and 0 otherwise. So j represents any position in our permutation, 1 <= j <= n.

We now try to figure out what the probability is that a given indicator variable is 1. It is important to note that although the probabilities for the indicator variables are not independent, linearity and symmetry for indicator variables holds.

There are two cases to consider: 1) When the indicator variable represents the first or last spot; and 2) when the indicator variable represents some spot in between.

Case (1):

In case 1, IND(0) or IND(n), it is easy to see that to be a local maxima these terms must simply be greater than the number directly adjacent and there is only one adjacent number. Therefore, since the permutation is random, the probability that IND(0) is a local maxima is 1/2. Similarly for IND(n) the probability is 1/2. So we have 2 cases with probability 1/2.

Case (2):

In case 2, the places we consider must be larger than both numbers surrounding them. Therefore the probability that a specific spot is a local maxima (ie the probability that the indicator variable is 1) is 1/3. So we have n-2 cases where the probability is 1/3.

In total, we have the Expected Value of the indicator variables,

E(IND(0 to n)) = 2*1/2 + (n-2)*1/3 = (n+1)/3.

So our solution is (n+1)/3.

This solution may seem fairly simple but it is only because of the power of indicator variables and their usefulness in evaluating complex probability situations.

[…] Haley writes about a neat probability problem from the Putnam exam which looks harder than it really […]

By:

Carnival of Mathematics #43 « The Number Warrioron November 10, 2008at 1:43 pm