What is the expected maximum out of a sample (size N) from a geometric distribution? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T04:28:58Z http://mathoverflow.net/feeds/question/41604 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/41604/what-is-the-expected-maximum-out-of-a-sample-size-n-from-a-geometric-distributi What is the expected maximum out of a sample (size N) from a geometric distribution? Dimitris Andreou 2010-10-09T15:42:45Z 2010-10-10T00:50:42Z <p>Lets say I have a <a href="http://en.wikipedia.org/wiki/Geometric_distribution" rel="nofollow">geometric distribution</a> (of the number X of Bernoulli trials needed to get a success) with parameter <code>p</code> (success probability of a trial).</p> <p>Assume I randomly sample <code>n</code> elements from this distribution.</p> <p>My problem is: what is the expected <em>maximum</em> element of such a sample (it should depend on <code>n</code> I guess)? Hopefully it makes sense...</p> <p>For <code>n=1</code>, e.g. if I only pick a single element from the distribution, the answer would be the mean <code>1 / p</code> of the distribution. For samples of larger cardinalities?</p> http://mathoverflow.net/questions/41604/what-is-the-expected-maximum-out-of-a-sample-size-n-from-a-geometric-distributi/41614#41614 Answer by Mike Spivey for What is the expected maximum out of a sample (size N) from a geometric distribution? Mike Spivey 2010-10-09T17:18:35Z 2010-10-09T17:18:35Z <p>Here's an answer: $\sum_{i=1}^n \binom{n}{i} (-1)^{i+1} \frac{1}{1-q^i}$, where $q = 1-p$. Maybe someone else can help you simplify that further. </p> <p>The argument: Let $Y = \max\{X_1, X_2, \ldots, X_n\}$, where the $X_i$ are $n$ sampled values from the geometric distribution.</p> <p>Then $E[Y] = \sum_{k=0}^{\infty} P(Y>k) = \sum_{k=0}^{\infty} P(X_1 > k \text{ or } X_2 > k \text{ or } \cdots \text{ or } X_n > k)$.</p> <p>Applying the principle of inclusion-exclusion and the fact that the $X_i$ are iid, we have </p> <p>$P(X_1 > k \text{ or } X_2 > k \text{ or } \cdots X_n > k)=$</p> <p>$=\binom{n}{1} P(X_1 > k) - \binom{n}{2} P(X_1 > k)^2 \pm \cdots (-1)^{n+1} \binom{n}{n} P(X_1 > k)^n$. </p> <p>Since $P(X_1 > k) = q^k$, this sum becomes $\sum_{i=1}^n \binom{n}{i} (-1)^{i+1} q^{ki}$.</p> <p>Thus </p> <p>$E[Y] = \sum_{k=0}^{\infty} \sum_{i=1}^n \binom{n}{i} (-1)^{i+1} q^{ki} = \sum_{i=1}^n \binom{n}{i} (-1)^{i+1} \sum_{k=0}^{\infty} (q^i)^k$</p> <p>$= \sum_{i=1}^n \binom{n}{i} (-1)^{i+1} \frac{1}{1-q^i}.$</p> http://mathoverflow.net/questions/41604/what-is-the-expected-maximum-out-of-a-sample-size-n-from-a-geometric-distributi/41640#41640 Answer by Mike Spivey for What is the expected maximum out of a sample (size N) from a geometric distribution? Mike Spivey 2010-10-10T00:50:42Z 2010-10-10T00:50:42Z <p>Bennett Eisenberg's paper "On the expectation of the maximum of IID geometric random variables" (<em>Statistics and Probability Letters</em> 78 (2008) 135-143) gives both my answer already accepted by the OP and mentions the infinite sum you get if you take Michael Lugo's comment on my first answer. However, the author also says, "these expressions are not so useful" and "There is no... simple expression for... the expected value of the maximum of $n$ IID geometric random variables." The point of his paper is "to use simple Fourier analysis to show that $E(M_n^*) - \sum_{k=1}^n \frac{1}{\lambda k}$ is very close to 1/2 not only for moderate values of $\lambda$, but also for relatively small values of $n$ and that this difference is logarithmically summable to 1/2 for all values of $\lambda$." Here, $E(M_n^*)$ is the expectation requested by the OP, and $\lambda$ is defined by $q = 1-p = e^{-\lambda}$. (The $\lambda$ is the parameter for the corresponding exponential distribution.) The practical value of Eisenberg's result, of course, is the fact that $\sum_{k=1}^n \frac{1}{k}$ can be closely approximated by $\log n + \gamma$.</p>