Posted by: dhaleyjr | October 31, 2008

Stat Problem

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.

Advertisements

Responses

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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: