math problem - 10 numbered balls in a hat and 10 people select a ball

Hi -

If 10 numbered balls are placed into a hat and each of 10 people select a ball, then after round r=1, the expected high value is exactly 10.
All balls are placed back in the hat.
On round r=2, each of the 10 people selects a ball and adds that score to their score from round 1 and then calculates their average score.

What is the expected high average score after round r=2
Then round 3 and so forth till round r=n where n approaches infinity.

1) What is the expected highest average after r=2?
2) what is the expected highest average after r=3?
3) what is the expected highest average after r=n?
4) If the number of balls and number of people was 100 instead of 10, would the expected highest averages be 10 times the highest average for number of balls at ten?

My guesses without any math:
1) the person with a 10 after round 1 would expect to average a 5.5 on round two for an average of 7.75, however if his second round score is low, then some percentage of the time the person with a 6-9 score in round one will also have a high score in round 2, so I'm thinking 7.5 is a low bound for the expected high score after r=2
2) Here I'm thinking that 10+5.5+5.5/3 = 7.0 would be the lower bound for the expected high score
3) all scores have to approach 5.5 as n approaches infinity or am I missing something?
4) yes

Thanks kindly to anyone choosing to comment,

Tom
Sydney, Aus

It seems you have been tricked by question number 4.

You're correct on #3, which means you're wrong on #4. 55 isn't halfway between 1 and 100:-)

In round 2, the expected high score will exceed 7.75 as you suspected.

This is not an easy problem, but the scores will be skewed to the higher end.

It is possible, but not easy, to calculate the discrete probability of each total in round 2. I have calculated a few just to get the juices flowing:

Total
20, p=0.1; This one is the easiest, since you have a 10% chance of getting a 10 to follow the first 10.
19, p = 17/90; You have a 10% chance of getting a 10 followed by a 9, and you have a 10% chance of a 9 being followed by a 10, but you must subtract the intersection of these, which is the chance of getting a 10,9 and a 9,10 = 1/10*1/9.

...

11, p = 1/10!

Quote: rdw4potus

You're correct on #3,

Yes and no.
For the maximum to be 5.5, you need all the participants to have that exact average, since the total is always 55. This event is quite rare. Actually, whenever r is odd, it cannot happen!
So, the expected maximum is always strictly higher than 5.5.

As a consequence, there is a formal difference between how one player's average or the maximum average evolves. The former has always an expected 5.5; it is the variance that goes down, along with sqrt(r). The latter has never an expected 5.5, it simply approaches it asymptoticlally.
Beware when handling infinity.
In the latter case we speak of an asymptotic behaviour. In the former, we say the player's average "converges in probability" to 5.5.

But r is never infinity, so the interesting question remains: how does the expectation behave w.r.t. r ?


Also, this points a special light on question #4:
As r goes to infinity, the E(10) approaches 5.5 and the E(100) approaches 50.5. But when? From what values of r will E(100) be lower than 10x E(10)? (I expect it to be very late in the process.)

Quote: rusnak

1) What is the expected highest average after r=2?

8.76

Quote: rusnak

4) If the number of balls and number of people was 100 instead of 10, would the expected highest averages be 10 times the highest average for number of balls at ten?

For r=2, approximately 94.54.

------------------------------
After much hard (hand) calculations, I came to the formula of Emax (the expected maximum) for r=2:

Emax = b - SUMk=1 to b-1(k! kb-k ) /2b!

where b is the number of balls/people.

I have not found a similar formula for r>2. Firstly, with even b and odd r, the minimum highest average is not (b+1)/2. Secondly, the usual technique for the probability of a maximum (using the cumulative distribution function) is not an help; you still have to subdivide for every conditional path, leading to an exponentially growing number of calculations. For example, b=6 r=3 gives (6!)²=518400 profiles to extract.

Here is a table of some of the expected highest averages:

b	r = 2	r = 3	r = 4	r = 5	r = 6	r = 7	r = 8
2	1.75	1.75	1.6875	1.6875	1.65625	1.65625	1.63671875
3	2.58333	2.5	2.395833	2.38117
4	3.56250	3.27662	3.168132
5	4.30417
6	5.18125
7	6.0668
8	6.9592
9	7.8574
10	8.7606

It seems that the values converge very slowly to (b+1)/2, the minimum, as r gets large.

I have been supposing that it is a boardgame, where b payers are randomly assigned their turn in each round (r). Practically, it is doubtful that the game will last long enough for the Emax to approach the "equilibrium" value where each player has been treated "equally". It is, instead, to be expected that one player receive a royal share (= the maximum average) and, by symmetry, another be lagging way behind. As for practical matters, you can tell the complaining player that this is perfectly normal: he didn't have bad luck, it is the game that is unfair.