A Ball-Drawing problem

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

A Ball-Drawing problem

G H J

Reveal topic tags

probability and stats

L

G H BBookmark kLocked kLocked NReply

Source: Inspired by a certain daily routine of mine

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4 posts

#1 h Apr 24, 2025, 2:58 AM

Y by

There are N identical black balls in a bag. I randomly take one ball out of the bag. If it is a black ball, I throw it away and put a white ball back into the bag instead. If it is a white ball, I simply throw it away and do not put anything back into the bag. The probability of getting any ball is the same.
Questions:
1. How many times will I need to reach into the bag to empty it?
2. What is the ratio of the expected maximum number of white balls in the bag to N in the limit as N goes to infinity?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

10630 posts

#2 h Apr 24, 2025, 11:21 AM • 1 Y

Y by Vivacious_Owl

1. Suppose we have $k$ black and $l$ white balls in the bag. The quantity $f:=2k+l$ decreases by exactly 1 with each step. Hence we need exactly $2N$ steps to empty the bag. I will think about 2 at a later time.
I think we can use the reflection principle to count paths with a given maximum.

This post has been edited 2 times. Last edited by alexheinis, Apr 24, 2025, 5:00 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4 posts

#3 h Apr 24, 2025, 3:35 PM

Y by

Correct!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

651 posts

#4 h Apr 25, 2025, 7:51 AM • 2 Y

Y by GreenKeeper, Saucitom

Nice problem! What is the real source of the problem? ('Inspired by a certain daily routine' seems somewhat implausible: The problem is certainly very carefully designed.) Do you have references for the problem (and maybe a solution)?

I suspect a rigorous answer to part 2 will be tricky and technical: I don't think reflection principle will be useful due to the lack of symmetry.

Let me give some heuristics that are hopefully correct and should even give a stronger result. I will write $n = N$ for convenience. First of all we will represent the urn model by a random walk: Let $S_k$ denote the number of white balls in the bag at time $k$ (i.e. after $k$ steps). Note that $S_k = j$ implies that at time $k$ there are $j$ white balls and $n- \frac{k+j} 2$ black balls in the urn (which is consistent with alexheinis answer to part 1). Thus we have
$P(S_{k+1} = j+1| S_k = j) = \frac{n - \frac 1 2 (j+k)}{n + \frac 1 2 (j-k)} =: p_{k,j}$ and $P(S_{k+1} = j-1| S_k = j) = 1 - p_{k,j}$ . Thus $S_k$ , $0 \le k \le 2n$ is a random walk (on nonnegative integers) with increments $\pm 1$ . The increments however are not independent, and also depend on the time, so this is messy. So far this is rigorous. Now we want to consider $n \to \infty$ and scale time and space by $n$ .

If we had a simple random walk, scaling time by $n$ and space by $\sqrt n$ gives Brownian motion. In our random walk we locally should also expect random fluctuations to be of size $\sqrt n$ , so in the space scaling of $n$ , we should expect all randomness to dissapear, i.e. the paths of our random walk should converge to a deterministic curve. The slope of this curve should correspond to the local drift of the random walk, which is given by $2 p_{k,j} - 1$ . Introducing $t := \frac k n$ and $x := \frac j n$ , the above one-step-transition thus gives the differential equation
$x' = 2 \frac{1 - \frac 1 2 (x+t)}{1 + \frac 1 2(x-t) }-1 = \frac{2-t-3x}{2-t+x}.$ We also have the initial value $x(0) = 0$ . The maximum of $x$ on the interval $[0,2]$ should give the ratio of the maximum number of white balls in the bag to $n$ . Now this is a purely analytic problem. I don't know if one can solve the ODE by hand, but with help of wolfram we seem to get an implicit description of $x$ , namely
$\ln(1-\frac 1 2 (x+t)) + \frac{x}{1 - \frac 1 2 (x+t)} = 0.$ At the maximum of $x$ we have $x' = 0$ , i.e. $2-t-3x = 0$ and using this to eliminate $t$ in the above implicit description we get a maximum avlue of $x = \frac 1 e$ . I didn't double check my calculations and I also didn't perform simulations in order to see whether this is plausible, but it seems reasonable.

Note that (if there are no computational mistakes above), we get something stronger: The scaled random walk paths should converge to the above deterministic curve, so the scaled
maximum should not just converge to $\frac 1 e$ in expectation, but also in distribution. (If true, this should also be visible in simulations.)

The above obviously is not a proof. It would require some effort to show the claimed convergence of the random walk paths, but in priciple it should be possible.There also might be simpler arguments for the convergence in expectation, e.g. with arguments of a combinatorial flavor.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1701 posts

#5 h Apr 25, 2025, 12:56 PM

Y by

solyaris wrote:

I don't know if one can solve the ODE by hand

https://en.wikipedia.org/wiki/Homogeneous_differential_equation#Special_case

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

651 posts

#6 h Apr 25, 2025, 2:29 PM

Y by

Thanks for pointing that out! So indeed the ODE can be solved by hand (and I would hope that this reproduces the solution given by Wolfram alpha).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1701 posts

#7 h Apr 25, 2025, 8:42 PM • 1 Y

Y by Saucitom

Yeah the solution of the ODE is correct. Also I wrote a simple simulation in Python:

import numpy as np
 
N = 10**4
SIMS = 10**3
 
maxs = []
 
for _ in range(SIMS):
    blacks = N
    whites = 0
    whites_max = 0
 
    for _ in range(2 * N):
        random_ball = np.random.randint(blacks + whites)
 
        if random_ball < blacks:
            blacks -= 1
            whites += 1
        else:
            whites -= 1
 
        whites_max = max(whites_max, whites)
 
    maxs.append(whites_max)
 
print(np.mean(maxs) / N)
print(np.exp(-1))

The results look promising. For $N=10^4$ and $10^3$ simulations I got approximately $0.3702$ , a decent match for $1/e\doteq0.3679$ . I might try the distribution later if nobody beats me to it.

UPDATE: For $N=10^5$ and $10^4$ simulations I got approximately $0.3684$ , so it seems that $1/e$ is indeed correct.

This post has been edited 3 times. Last edited by GreenKeeper, Apr 26, 2025, 7:36 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4 posts

#8 h Apr 26, 2025, 1:40 AM • 1 Y

Y by Saucitom

Glad you like the problem! I came up with it while taking vitamin pills. Dose of one pill was too high so I would take half a pill and put the other back in the bottle. I noticed that at first when the bottle was new I mostly got a whole pill each time, but then as the halves accumulated they started to appear more often and after a little it’s mostly them you get with occasional wholes until the end. This was counterintuitive to me at the time. Initially I assumed that they would equalize in number and remain in this equilibrium until the very end. But as often the case with probabilities our intuition fails. If you plot the graphs of white and black balls you’ll see that after crossing the white ball curve stays above the black one until the very end. Moreover the difference between them after crossing grows for a while, reaches max at a point and starts decreasing towards the end.

Considering the continuous case in your notation the differential equations of the process are dy/dt=-y/(x+y) and dx/dt=(y-x)/(x+y). where y is the ratio of the expected number of black balls in the bag to N in the limit as N goes to infinity. From them follows the invariant t+x+2y=2 and the solution t=2+y(ln(y)-2) (considering the initial conditions t=0, x=0, y=1). Now dx/dt=0 when y=x which gives x=y=1/e at t=2-3/e

BTW the invariant could be deduced directly from the problem. Consider the number of times you need to touch the balls to empty the bag. Think of it not as if you replace one ball for another but simply change its color by touching it. In the middle of the process it’s T times you have already touched the balls + X times for each white ball you have left and 2Y times for each black one. It’s 2N in total. So T+X+2Y=2N

The max difference between the white and black balls I was referring to at beginning can be inferred from the differential equations (x-y)'=(2y-x)/(x+y)=0 so x=2y and y=1/e^2, x=2/e^2, t=2-4/e^2

This post has been edited 1 time. Last edited by Vivacious_Owl, Apr 26, 2025, 1:48 AM
Reason: typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

87 posts

#9 h Apr 26, 2025, 3:28 PM

Y by

Very nice discussion! This problem reminds me of a variation of Polya Urn, which appears last year at Miklos-Schweitzer (P11). In both cases, one can approximate the solution with an ODE.

This post has been edited 1 time. Last edited by Saucitom, Apr 26, 2025, 3:34 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4 posts

#10 h Apr 28, 2025, 6:15 PM

Y by

The next step would be to generalize it to an arbitrary number of ball colors (or better in this case mark them with numbers maybe). Say initially there are N balls marked 0 in the bag. Then you randomly pick a ball and replace k-th ball number with a ball marked k+1. It could be a separate post with a beautiful and well known result!

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a