3
$\begingroup$

$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.

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

  • 1
    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?2012-04-28
  • 0
    As B and C are bounds, your simulation should always be between them. Unfortunately, B and C aren't too close.2012-04-28
  • 0
    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.2012-04-29
  • 0
    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?2012-04-29
  • 0
    This is probably an approximate solution: http://math.stackexchange.com/questions/138496/approximate-solution-for-an-exponential-equation#comment318868_1384962012-04-29

0 Answers 0