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?