I thought up this expected value problem:

Two hundred people are each assigned an integer from 1-100 so that there is a pair of each number. They are standing outside of a large waiting room. A random person will enter the room, one at a time. If their pair is there, they both continue on their way, otherwise they wait in the room until their pair arrives.

This goes on until there are no people left outside of the waiting room.

Question: What is the expected value of what will be the greatest sum of the values in the waiting room? A pair that immediately leaves doesn't contribute to the sum.

My thoughts: The lower bound is clearly 100, if everyone got their pair immediately. The upper bound is 1+2+3+...+100 = 5050, if there were no pairs for the first 100 people. In the simplified case of 4 people (1,1,2,2) there are 8 orders that will lead to a 2 and 1 being in the room at the same time and 16 orders of 2 being alone, so the expected value should be $\frac{8(2+1)+16(2)}{4!} = 2 \frac 13$. How can this idea be applied to the larger group?

  • 3
    $\begingroup$ I am confused between the "room" and the "waiting room" Also, where does "a pair that immediately leave..." go to ? Please state the problem clearly. $\endgroup$ Jan 14 at 6:24
  • 2
    $\begingroup$ I interpret it as the following: let $(x_1, \ldots, x_{200})$ be random (multi-)permutation of $(1,1,2,2,\ldots, 100, 100)$. Let $A_n = \{i \leq n | \forall j \leq n j \neq i \implies x_i \neq x_j\}$ and $f(n) = \sum_{i \in A_n} x_i$. What is $E(\max f(n))$? $\endgroup$ Jan 14 at 7:17
  • $\begingroup$ I think your example is mixed up, it should be $8\times 2 + 16\times (2+1)$ instead. $\endgroup$
    – Vepir
    Jan 14 at 10:00
  • 1
    $\begingroup$ For $1\le n\le 8$, brute force calculation yields $$ e(1)=1\\ e(2)=\frac{8}{3}\approx 2.666666667\\ e(3)=\frac{221}{45}\approx 4.911111111\\ e(4)=\frac{818}{105}\approx 7.790476190\\ e(5)=\frac{6386}{567}\approx 11.26278660\\ e(6)=\frac{796163}{51975}\approx 15.31819144\\ e(7)=\frac{77190329}{3869775}\approx 19.94698116\\ e(8)=\frac{16054373936}{638512875}\approx 25.14338327 $$ $\endgroup$
    – quasi
    Jan 14 at 16:40
  • 1
    $\begingroup$ For n=100, a simulation yields $e(100)\approx 2763$. $\endgroup$
    – quasi
    Jan 14 at 16:41

1 Answer 1


I interpret it as the following: let $(𝑥_1,…,𝑥_N)$ be random (multi-)permutation of $(1,1,2,2,…,N,N)$. Let $𝐴_𝑛=\{i \leq n|\forall 𝑗 \leq 𝑛 j \neq i \implies 𝑥_i \neq x_j\}$ and $$f(n)=\sum_{i \in A_n}x_i.$$ What is $E[\max_n(f(n))]$?

I do not have a full answer, but I will give a lower bound. Define random variables $X_{i,n} = i$ if exactly one copy of $i$ appears in the permutation in the first $n$-elements, and otherwise $0$. Then $f(n) = \sum_{i=1}^N X_{i,n}$.

Equivalently, we may say that $X_{i,n} = 0$ iff either both copies of $i$ are in the first $n$ elements of the list, or neither are.

The probably that they are both in the first $n$ elements is $$\frac{{n \choose 2}}{{2N \choose 2}}$$ since there are ${n \choose 2}$ such pairs out of ${2N \choose 2}$ total. Similarly, the probability that both pairs do not appear in the first $n$ elements is $$\frac{{2N-n \choose 2}}{{2N \choose 2}}.$$ Thus

$$P(X_{i,n} = i) = 1-\frac{{n \choose 2}+{2N-n \choose 2}}{{2N \choose 2}}$$

and so $$E[X_{i,n}] = i\left(1-\frac{{n \choose 2}+{2N-n \choose 2}}{{2N \choose 2}}\right).$$

Then \begin{align*} E[f(n)] &= E[\sum_{i=1}^N X_{i,n}]\\\\ &= \sum_{i=1}^N E[X_{i,n}]\\\\ &= \left(\frac{N(N+1)}{2}\right)\left(1-\frac{{n \choose 2}+{2N-n \choose 2}}{{2N \choose 2}}\right). \end{align*}

Now since $\max f(n) \geq f(i)$ for any $i$, we have $E(\max(f(n)) \geq E[f(i)]$ for any $i$. Choosing $i = N$ and simplifying then gives

$$E[\max f(n)] \geq \left(\frac{N}{2N-1}\right)\left(\frac{N(N+1)}{2}\right).$$

In a simulation, taking $100$ random permutations for each $N$ from $1$ to $500$, the bound seems not far off as $N$ becomes large:

enter image description here

For the particular case $N=100$ the bound is about 9% low.


You must log in to answer this question.

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