Using Indicator Variables to Calculate Expected Values

Indicator variables can often be used to find an expected value when doing the calculation directly from the definition would be quite difficult.  This post will look at a couple of examples and give references to several more.

First example

One of the classic examples of the use of indicator variables is to find the expected number of fixed points F_n in a permutation on n elements.  (Since I’ve been posting on problems related to the number of fixed points in a permutation lately, it seems appropriate to continue this trend.)

For a given permutation \sigma, define the indicator variable I_j such that \displaystyle I_j = \begin{cases} 1, & \text{ if } \sigma(j) = j; \\ 0, & \text{ otherwise}. \end{cases}

Then, for any permutation \sigma, F_n = \sum_{j=1}^n I_j.  By linearity of expectation, E[F_n] = \sum_{j=1}^n E[I_j].  But E[I_j] = P(\sigma(j) = j) = \frac{1}{n}.  Thus we have \displaystyle E[F_n] = \sum_{j=1}^n \frac{1}{n} = 1.

Therefore the expected number of fixed points in a permutation is, perhaps surprisingly, 1, regardless of the size of the permutation!  Obtaining this via the definition would require first counting the number of permutations with exactly k fixed points.  This could be done, but it would be much more complicated than the simple calculation here.

There are plenty of other examples.  I’ll describe a second (classic) one and then give references to some others.

Second example

Suppose you are tossing m balls into n bins.  Each ball is equally likely to land in each bin, and the ball tosses are independent.   What’s the expected number of bins that contain exactly k balls?

Again, let I_j = \begin{cases} 1, & \text{ if bin } j \text{ contains } k \text{ balls}; \\ 0, & \text{ otherwise}. \end{cases}

Then E[I_j] is the probability that bin j contains exactly k balls.  This is \binom{m}{k} \frac{(n-1)^{m-k}}{n^m}.  (Choose which k of the m balls will go into bin j, then choose which of the other n-1 bins will hold the remaining m-k balls, divided by the total number of ways to distribute m balls among n bins.)

Thus, if we denote the number the number of bins that contain exactly k balls by X_k, we have \displaystyle E[X_k] = \sum_{j=1}^n E[I_j] = \binom{m}{k} \frac{(n-1)^{m-k}}{n^{m-1}}.

More examples

See also Section 7.2 of Sheldon Ross’s A First Course in Probability [1] or one of the following math.SE questions:

  1. Dinesh’s answer to “How many bins do random numbers fill?”
  2. Byron Schmuland’s answer to “Find the expectation.”
  3. joriki’s answer to “Expectation of the cardinality of the intersection of two subsets.”  (I particularly like this one.  It hadn’t occurred to me at first to use indicator variables.)
  4. My answer to “Expected number of neighbors.”

Here are two more complicated examples.

  1. My answer to “Who has the upper hand in a generalized game of Risk?”  This question asks for the expected number of casualties suffered by the attacker in a generalized game of Risk.  The probabilities associated with the indicator variables do not come out as nicely as in the other examples I’ve given, and the resulting expectation is a quadruple sum.  Still, I’m not sure how one would find the requested expected value without using indicator variables.
  2. My answer to “How to calculate the expected number of distinct items when drawing pairs?”  This example is different because the indicator variables can take on the values 0, 1, or 2.  That makes the analysis more complicated than in most of the other examples I’ve given, but the use of indicator variables still simplifies the calculation on this problem considerably from what it would be otherwise.

References

1.  Sheldon M. Ross, A First Course in Probability, 7th edition, Prentice Hall, 2005.

Advertisements
This entry was posted in probability. Bookmark the permalink.

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