# Expectation of the Largest Number

### A Letter (and Solution 1)

Dear Alexander,

I am writing about your Symmetry Principle as you applied it to the problem of the expected number of cards to be dealt in order to get the first ace.

I came up with the probability puzzle (AB: see above) and had been working on it.

After tediously solving it by normal means, I realized that my problem was the same as your ace problem. Using the same Symmetry Principle logic as you did to solve your ace problem: The $n$ drawn balls divide, by rank, the remaining $N-n$ balls in the urn into $n+1$ groups of average size $\displaystyle \frac{N-n}{n+1}.$ The last group is from ball number $\displaystyle \left\lfloor\frac{n}{n+1}\cdot (N+1)\right\rfloor +1$ to ball number $N.$ The ball just before the first ball of the last group is the expected highest ball drawn:

$\displaystyle E(max) = \left\lfloor\frac{n}{n+1}\cdot (N+1)\right\rfloor.$

It occurred to me that a little more can be squeezed out of these problems with more use of symmetry. By symmetry, the expected minimum is given by:

\displaystyle \begin{align} E(min) &= \left\lfloor 1 - \frac{n}{n+1}\cdot (N+1)\right\rfloor\\ &= \left\lfloor \frac{1}{n+1}\cdot (N+1)\right\rfloor, \end{align}

which is the same as the answer to your ace problem. The formulas for expected minimum and maximum can be generalized to any rank:

$\displaystyle E(k) = \left\lfloor \frac{k}{n+1}\cdot (N+1)\right\rfloor.$

for $k = 1$ to $n,$ where $k$ is the rank from smallest to largest.

### Solution 2

For $k$ to be the largest ball, choose $k$ and $n-1$ balls from the first $k-1$ balls. Thus, the required expectation value is

\displaystyle \begin{align} E&=\frac{\sum_{k=n}^{N} k {k-1\choose n-1}}{{N\choose n}}=\frac{\sum_{k=n}^{N} n{k\choose n}}{{N\choose n}} \\ &=\frac{n}{{N\choose n}}\left[{n\choose n}+{n+1\choose n}+\ldots+{N\choose n}\right] \\ &=\frac{n}{{N\choose n}}{N+1\choose n+1}=\frac{n(N+1)}{(n+1)}. \end{align}

### Solution 3

1) Drawing without replacement, we can make use of the hypergeometric distribution for the distribution of $Z$, the max of an $n$ size sub-sample of $1,2,\ldots,N$; with mass function $\mathbb{P}(Z=z)=\phi(.)$:

$\displaystyle \phi (n,N,z)=\frac{\binom{N-z-1}{n-1}}{\binom{N-z}{n}}=\frac{n}{N-z}$

The expectation can be written as follows:

\displaystyle\begin{align}\mathbb {E}(Z)&=\sum _{i=0}^{N-n} (N-i) \phi (n,N,i) \prod _{j=0}^{i-1} (1-\phi (n,N,j))=\frac{n \left(n N-\frac{\Gamma (-N)}{\Gamma (-n-1) \Gamma (n-N)}+n+N+1\right)}{(n+1)^2}\\ &= \frac{n N}{n+1}+\frac{n}{n+1}+\underbrace{ \frac{n \sin (\pi n) \Gamma (n+1) \csc (\pi N) \sin (\pi (n-N)) \Gamma (-n+N+1)}{\pi (n+1) \Gamma (N+1)}}_{=0} =\frac{n (N+1)}{n+1}. \end{align}

2) Drawing with replacement, we have a discrete uniform distribution with cumulative $F(n)=\frac{x}{N}$. The cumulative probability of $Z$ is, by standard argument (all $x$ below $z$), $\displaystyle F(Z\geq z)=(\frac{z}{N})^n$.

The expectation becomes:

$\displaystyle \mathbb{E}(Z) =\sum _{i=1}^N i \left(\left(\frac{i}{N}\right)^n-\left(\frac{i-1}{N}\right)^n\right)$

### Acknowledgment

The above is the content of an anonymous comment left at an earlier page. Solution 2 is by Amit Itagi. Solution 3 is by N. N. Taleb.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 3, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://www.cut-the-knot.org/Probability/ExpectationOfMaximum.shtml", "fetch_time": 1524644801000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2018-17/segments/1524125947759.42/warc/CC-MAIN-20180425080837-20180425100837-00090.warc.gz", "warc_record_offset": 747667649, "warc_record_length": 14687, "token_count": 1092, "char_count": 3253, "score": 4.625, "int_score": 5, "crawl": "CC-MAIN-2018-17", "snapshot_type": "longest", "language": "en", "language_score": 0.8416599631309509, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00048-of-00064.parquet"}