Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was reading about the german tank problem and they say that in a sample of size $k$, from a population of integers from $1,\ldots,N$ the probability that the sample maximum equals $m$ is:

$$\frac{\binom{m-1}{k-1}}{\binom{N}{k}}$$

This make sense. But then they take expected value of the sample maximum and claim:

$$\mu = \sum_{m=k}^N m \frac{\binom{m-1}{k-1}}{\binom{N}{k}} = \frac{k(N+1)}{k+1}$$

And I don't quite see how to simplify that summation. I can pull out the denominator and a $(k-1)!$ term out and get:

$$\mu = \frac{(k-1)!}{\binom{N}{k}} \sum_{m=k}^N m(m-1) \ldots (m-k+1)$$

But I get stuck there...

share|improve this question
add comment

4 Answers

up vote 5 down vote accepted

Call $B_k^N=\sum\limits_{m=k}^N\binom{m-1}{k-1}$.


Fact 1: $B_k^N=\binom{N}{k}$ (because the sum of the masses of a discrete probability measure is $1$ or by a direct computation).


Fact 2: For every $n\geqslant i\geqslant 1$, $n\binom{n-1}{i-1}=i\binom{n}{i}$.


Now to the proof.

Fact 2 for $(n,i)=(m,k)$ gives $\sum\limits_{m=k}^Nm\binom{m-1}{k-1}=\sum\limits_{m=k}^Nk\binom{m}{k}=k\sum\limits_{m=k+1}^{N+1}\binom{m-1}{(k+1)-1}=kB_{k+1}^{N+1}$.

Fact 1 gives $B_{k+1}^{N+1}=\binom{N+1}{k+1}$.

Fact 2 for $(n,i)=(N+1,k+1)$ (or a direct computation) gives $(k+1)B_{k+1}^{N+1}=(N+1)B_k^N$.

Finally, $\mu=\dfrac{kB_{k+1}^{N+1}}{B_k^N}=k\dfrac{N+1}{k+1}$.


Edit The same method yields, for every $i\geqslant0$, $$ \mathrm E(X(X+1)\cdots(X+i))=\frac{k}{k+i+1}(N+1)(N+2)\cdots(N+i+1). $$

share|improve this answer
    
Wow that is an elegant and slick solution. Thanks! –  Palace Chan Sep 18 '11 at 20:45
1  
+1 I love it when you can bootstrap a formula derived probabilistically into a related formula for expectation. –  Byron Schmuland Sep 21 '11 at 21:53
add comment

Here is another way of looking at the problem that uses the natural symmetry.

The samples of size $k$ are in one-to-one correspondence with the sequence of "gaps" between the observations (via the sequence of order statistics):

$$\{x_1,x_2,\dots, x_k\}\leftrightarrow x_{(1)}<x_{(2)}<\cdots <x_{(k)} \leftrightarrow (G_1,G_2,\dots, G_{k+1})$$

Here we define $G_1=x_{(1)}$, $G_j=x_{(j)}-x_{(j-1)}$ for $2\leq j\leq k$, and $G_{k+1}=(N+1)-x_{(k)}$. This correspondence shows that $G_1,G_2,\dots, G_{k+1}$ are exchangeable random variables, in particular, they are identically distributed.

Since $\sum_{j=1}^{k+1} G_j=N+1$ identically, the expectations of these $k+1$ identically distributed random variables must be $\mathbb{E}(G_j)={N+1\over k+1}$.

In particular, $\mathbb{E}(G_{k+1})=\mathbb{E}((N+1)-x_{(k)})={N+1\over k+1}$ which implies $$\mathbb{E}(\mbox{Maximum})=\mathbb{E}(x_{(k)})=(N+1)- {N+1\over k+1}={k\over k+1} (N+1).$$

Similarly, we see that the expected values of the order statistics $\mathbb{E}(x_{(1)}),\mathbb{E}(x_{(2)}),\dots, \mathbb{E}(x_{(k)})$ are evenly spread out from ${1\over k+1} (N+1)$ to ${k\over k+1} (N+1).$

See this post for more questions about these gaps.

share|improve this answer
add comment

Alternatively, $$\mu = \sum_{m=k}^N m \frac{\binom{m-1}{k-1}}{\binom{N}{k}} = \sum_{m=k}^{N}\frac{m! k!(N-k)!}{N!(k-1)!(m-k)!}$$ $$= k\frac{k! (N-k)!}{N!} \sum_{m=k}^N \binom{m}{m-k} = k\frac{k! (N-k)!}{N!} \binom{N+1}{N-k}$$ $$= k\frac{k! (N-k)! (N+1)}{N! (N-k)! (k+1)!} = k\frac{N+1}{k+1}$$

where $$\sum_{m=k}^N \binom{m}{m-k} = \sum_{i=0}^{N-k} \binom{k+i}{i} = \binom{N+1}{N-k}$$ can be seen from Pascal's Triangle.

share|improve this answer
add comment

We know that $$\mu = \sum_{m=k}^N m \frac{\binom{m-1}{k-1}}{\binom{N}{k}}$$ $$= \sum_{m=k}^{N}m \frac{(m-1)! k!(N-k)!}{N!(k-1)!(m-k)!}$$

$$= \frac{k!(N-k)!}{N!(k-1)!} \sum_{m=k}^{N} m \frac{(m-1)!}{(m-k)!}$$

$$ = \frac{k (N-k)!}{N!} \sum_{m=k}^{N} \frac{m!}{(m-k)!}$$

The expression on the right is a sum of falling factorials.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.