9
$\begingroup$

Lets say I have a geometric distribution (of the number X of Bernoulli trials needed to get a success) with parameter p (success probability of a trial).

Assume I randomly sample n elements from this distribution.

My problem is: what is the expected maximum element of such a sample (it should depend on n I guess)? Hopefully it makes sense...

For n=1, e.g. if I only pick a single element from the distribution, the answer would be the mean 1 / p of the distribution. For samples of larger cardinalities?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ This is a good question but probably a bit low-level for MO. I suggest taking it to math.stackexchange.com . $\endgroup$
    – Michael Lugo
    Commented Oct 9, 2010 at 17:11
  • 1
    $\begingroup$ While I understand the downvote and the support of Michael's original suggestion to move the question to Math Stack Exchange, I think that there is more to this question than appears at first glance and that it is appropriate for MO. I finally had a chance to dig through my files at school this afternoon, and I found a research paper that addresses the question. See my second answer. $\endgroup$
    – Mike Spivey
    Commented Oct 10, 2010 at 0:50
  • $\begingroup$ For what it's worth, there's a post on StackExchnage $\endgroup$
    – Lee David Chung Lin
    Commented Mar 17, 2018 at 2:18

2 Answers 2

Reset to default
14
$\begingroup$

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.

The argument: Let $Y = \max\{X_1, X_2, \ldots, X_n\}$, where the $X_i$ are $n$ sampled values from the geometric distribution.

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)$.

Applying the principle of inclusion-exclusion and the fact that the $X_i$ are iid, we have

$P(X_1 > k \text{ or } X_2 > k \text{ or } \cdots X_n > k)=$

$=\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$.

Since $P(X_1 > k) = q^k$, this sum becomes $\sum_{i=1}^n \binom{n}{i} (-1)^{i+1} q^{ki}$.

Thus

$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$

$= \sum_{i=1}^n \binom{n}{i} (-1)^{i+1} \frac{1}{1-q^i}.$

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ It's a bit simpler to note that $P(X_1 > k \hbox{or} \ldots \hbox{or} X_n > k) = 1 - P(X_1 \le k \hbox{and} \ldots \hbox{and} X_n \le k) = 1-P(X_1 \le k)^n$. $\endgroup$
    – Michael Lugo
    Commented Oct 9, 2010 at 17:23
  • 1
    $\begingroup$ @Michael: I always tell my students to look out for using the complement on probability problems, and so I'm a bit embarrassed that I didn't catch it myself here! However, in this case, if you take the complement approach, when you get to the infinite sum you have $\sum_{k=0}^{\infty} (1 - (1-q^k)^n)$. This is going to be difficult unless you then express $(1 - q^k)^n$ using the binomial formula. So I think for this problem inclusion-exclusion turns out to be of about the same degree of difficulty as using the complement. $\endgroup$
    – Mike Spivey
    Commented Oct 9, 2010 at 17:42
  • $\begingroup$ You're right. I had worked out the solution in my head and seem to have done it wrong. $\endgroup$
    – Michael Lugo
    Commented Oct 9, 2010 at 17:50
  • 1
    $\begingroup$ Also, this is a nice problem! I might assign it when I teach probability next semester. $\endgroup$
    – Michael Lugo
    Commented Oct 9, 2010 at 17:53
  • $\begingroup$ I do wish I had paid more attention to probabilities when at University, my head aches at anything above simple... :-/ thanks for the answer and comments! $\endgroup$
    – Dimitris Andreou
    Commented Oct 9, 2010 at 19:24
8
$\begingroup$

Bennett Eisenberg's paper "On the expectation of the maximum of IID geometric random variables" (Statistics and Probability Letters 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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .