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.

$N+M$ people play a game of balls.

Initially, N people hold N green balls (each person holds a ball), and M people hold no balls. Assume $M<N$.

Then, M red balls are divided randomly - each ball is given to a person selected at random from among all M+N people.

Whenever a person that accepts a ball, holds a green ball - that ball is taken, painted in red, and given to a person selected at random from among all M+N people.

This process must end sometime, because each ball will be taken at most once (when it is green).

At the end of this process, what is the expected number of people, P, that have no balls?

(NOTE: this is a revised version of a question I asked before, about land-ownership).

I currently only have some bounds:

A. Certainly $P \le M$, since a person that initially holds a green ball, will always have at least one ball.

B. Moreover, if we divide only the original M red balls, and do not re-divide any green ball, then the probability of NOT getting any red ball is: $$(1 - \frac{1}{N+M})^M \approx exp (-\frac{M}{N+M})$$

Therefore: $$ P \le M exp (-\frac{M}{N+M}) $$

C. If we divide all $M+N$ balls, then the probability of NOT getting any ball is: $$(1 - \frac{1}{N+M})^{N+M} \approx exp (-1)$$

Therefore: $$ P \ge M exp (-1)$$

My simulations show that the actual number is, usually, between these bounds, but I couldn't find an exact expression for it. Can you help?


In case this helps: here are my simulation results (mean of 100 runs; in all runs $M+N=100$). In each line there are 4 numbers: M, B, P, C (where B and C are the corresponding bounds). P is always between B and C:

50 30.33 23.36 18.39

49 30.02 22.56 18.03

48 29.7 22.19 17.66

47 29.38 21.89 17.29

46 29.04 21.85 16.92

45 28.69 21.5 16.55

44 28.34 21.1 16.19

43 27.97 20.6 15.82

42 27.6 20.39 15.45

41 27.21 19.71 15.08

40 26.81 19.65 14.72

39 26.41 19.58 14.35

38 25.99 19.12 13.98

37 25.56 18.78 13.61

36 25.12 18.25 13.24

35 24.66 17.81 12.88

34 24.2 17.19 12.51

33 23.72 16.96 12.14

32 23.24 16.92 11.77

31 22.74 16.72 11.4

30 22.22 16.14 11.04

29 21.7 15.58 10.67

28 21.16 15.31 10.3

27 20.61 14.95 9.93

26 20.05 14.31 9.56

25 19.47 14.13 9.2

24 18.88 13.13 8.83

23 18.27 13.45 8.46

22 17.66 12.55 8.09

21 17.02 12.28 7.73

20 16.37 11.52 7.36

19 15.71 11.56 6.99

18 15.03 10.69 6.62

17 14.34 10.66 6.25

16 13.63 10.01 5.89

15 12.91 9.46 5.52

14 12.17 9.04 5.15

13 11.42 8.47 4.78

12 10.64 7.82 4.41

11 9.85 7.48 4.05

10 9.05 6.62 3.68

9 8.23 6.21 3.31

8 7.38 5.72 2.94

7 6.53 4.94 2.58

6 5.65 4.26 2.21

5 4.76 3.86 1.84

4 3.84 3.13 1.47

3 2.91 2.25 1.1

2 1.96 1.59 0.74

1 0.99 0.89 0.37

share|improve this question
    
Is it true to say that the number of people with no balls is equivalent to the number of balls that go to people who have already (at least once) received a ball? –  Ronald Apr 28 '12 at 20:56
    
As B and C are bounds, your simulation should always be between them. Unfortunately, B and C aren't too close. –  Ross Millikan Apr 28 '12 at 23:08
    
Ronald, yes, as the total number of balls is equal to the total number of people ($M+N$), certainly the number of people with no balls is equal to the number of "extra" balls that are held by other people. –  Erel Segal Halevi Apr 29 '12 at 4:42
    
I think an equivalent question may be: What is the expected number of balls that will be divided? This is certainly somewhere between M and (N+M), but what exactly? –  Erel Segal Halevi Apr 29 '12 at 9:37
    
This is probably an approximate solution: math.stackexchange.com/questions/138496/… –  Erel Segal Halevi Apr 29 '12 at 19:19

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.