In my last post I derived the formula for the expected maximum of n independent and identically distributed (iid) exponential random variables. If each random variable has rate parameter , then the expected maximum is , where is the nth harmonic number.
This post considers the discrete version of the same problem: the expected maximum of n independent and identically distributed geometric random variables. Unfortunately, there is no known nice, closed-form expression for the expected maximum in the discrete case. However, the answer for the corresponding exponential random variables turns out to be a good approximation.
Let be n iid geometric(p) random variables. Let denote the maximum of the variables. Let . Let the rate parameter for the corresponding exponential distribution be . Now, we have
as the cumulative distribution function of a geometric(p) random variable is .
By viewing the infinite sum as right- and left-hand Riemann sum approximations of the corresponding integral we obtain
Now, let’s take a closer look at the integral that occurs on both sides of this inequality. With the variable switch we have
proving the fairly tight bounds
We can obtain a more precise approximation by using the Euler-Maclaurin summation formula for approximating a sum by an integral. Up to a first-order error term, it says that
yielding the approximation
with error term given by
One can verify that this is quite small unless n is also small or q is extreme.
See also Bennett Eisenberg’s paper “On the expectation of the maximum of IID geometric random variables,” Statistics and Probability Letters 78 (2008), 135-143.