The Expected Maximum of Independent and Identically Distributed Exponential Random Variables

Finding the expected maximum of independent and identically distributed (iid) exponentially distributed random variables is a standard calculation in an undergraduate course in probability theory.  This post goes through the details of that calculation.  (My next post will address the more difficult question of the expected maximum of iid geometric random variables.)

There are three properties of exponential random variables that we need.

  1. Exponentially distributed random variables are memoryless.  Formally, if X is exponentially distributed, then P(X > t+s | X > s) = P(X > t).  Less formally, suppose that the lifetime of an electronic component is exponentially distributed.  The memoryless property says that the probability that the component will last at least t units longer, given that the component has lasted s units of time, is independent of the value of s.
  2. The minimum of n exponentially distributed random variables with rate parameters \lambda_1, \lambda_2, \ldots, \lambda_n is itself exponentially distributed with rate parameter \sum_{i=1}^n \lambda_i.  (For a proof, see the Wikipedia page on the exponential distribution.)
  3. The exponential distribution is a continuous distribution.  (This is a very basic property of the exponential distribution.  However, the geometric distribution has the first two properties as well, yet its expected maximum is more complicated.)

Now, suppose we have n iid exponential(\lambda) random variables, and let T_i be the ith smallest of these.  Since T_1 is exponential(n \lambda), E[T_1] = \frac{1}{n \lambda}.

Since exponential random variables are continuous, the probability that any two of the n random variables have the same value is 0.  Thus the n-1 other random variables all have values larger than T_1.  However, the memoryless property says knowledge of T_1 essentially “resets” the values of the other random variables, so that the time between T_1 and T_2 is the same (distributionally) as the time until the first of n-1 iid exponential(\lambda) random variables takes on a value.  Thus E[T_2 - T_1] = \frac{1}{(n-1) \lambda}.  

Applying the same logic, we get that, for 1 \leq i \leq n-1, E[T_{i+1} - T_i] = \frac{1}{(n-i) \lambda}.  Thus the expected value of the maximum of the n random variables is

\displaystyle E[T_n] = E\left[T_1 + \sum_{i=1}^{n-1} (T_{i+1}-T_i) \right] = \sum_{i=0}^{n-1} \frac{1}{(n-i) \lambda} = \sum_{i=1}^n \frac{1}{i \lambda} = \frac{H_n}{\lambda},

where H_n is the nth harmonic number.

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

2 Responses to The Expected Maximum of Independent and Identically Distributed Exponential Random Variables

  1. inordinatum says:

    Hi Mike,

    this is a very interesting article! I rechecked your final formula for E[T_n] directly using the cumulative distribution function of the maximum, and it works perfectly for \lambda=1. However, for \lambda \neq 1 I can’t seem to make it work (I actually get \sum_{k=1}^n (-1)^{k+1} \binom{n}{k} \lambda^{k-1}/k, which seems to be different since it involves all powers of \lambda). Could you maybe elaborate a bit on how you perform the calculation for arbitrary \lambda?

    Thanks!
    Alexander

  2. mzspivey says:

    Hi, Alexander. I’m glad you like the post! I’m not quite sure what you’re asking me to do by elaborating on the calculation for arbitrary \lambda, though, since the calculation for arbitrary \lambda is what the whole post is about. Is there a particular part of the derivation that is confusing?

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