27

Consider the following recurrence relation in two variables: f(a,b)=aa+bf(a1,b)+ba+bf(a+1,b1) for positive integers a and b, with the boundary conditions f(0,b)=0 for integers b>0 and f(a,0)=1 for integers a0.

I believe that f(1,n) converges to 1 as n tends to infinity. However I can't see how to prove it.

Numerically the convergence is slow.

@FedorPetrov's reformulation of the recurrence as a probability question is as follows (lightly edited). Consider an urn with a White and b Black balls. Take a random ball, eat it if it is White and recolor it White (returning to the urn) if it is Black. Then f(a,b) is the probability that when the balls become of the same color, this color is White.

13
  • 4
    did a random walk question lead you to this recurrence? if so, can you state that problem (I just woke up and can't figure it out immediately) Commented Dec 10, 2023 at 8:04
  • 8
    @mathworker21 let be an urn with a White and b Black balls. Take a random ball, eat it if it is White and recolor it White (returning to the urn) if it is Black. Then f(a,b) is the probability that when the balls become of the same color, this color is White. Commented Dec 11, 2023 at 13:59
  • 1
    @mathworker21 The series Φ(x,y):=m,n=1f(m,n)nxm1yn satisfiesx2(1x)Φx(x,y)+(xy)yΦy(x,y)+x(12x)Φ(x,y)+y2Φy(0,y)=xy1xbut I do not quite see how to use it Commented Dec 11, 2023 at 19:45
  • 5
    The setup is from the "Pill problem" (AMM-problem E3429,(vol. 98(3) 1991, p.264) by Knuth and McCarthy)): A certain pill bottle contains m large pills and n small pills, where each large pill is equivalent to two small ones. Each day the patient chooses a pill at random, if a small pill is selected, (s)he eats it; otherwise (s)he breaks the selected pill and eats one half, replacing the other half, which is thenceforth considered to be a small pill. --You'll find some literature using this keyword.
    – esg
    Commented Dec 21, 2023 at 20:33
  • 4
    Following esg's comment, I found A drug-induced random walk by Daniel Velleman, Amer. Math. Monthly 121 (2014), 299-317. Commented Jan 18 at 2:58

5 Answers 5

6

The urn problem is equivalent to a continuous-time process where the balls behave independently.

Balls can be either Black, White, or Gone. For each ball, there's an independent Poission process of events at some fixed rate (say, λ=1). An event turns a Black ball into a White ball, and turns a White ball into a Gone ball (and turns a Gone ball into a Gone ball). Given an initial configuration of a White and b Black balls, what's the probability f(a,b) that the balls are all White (or Gone) before they are all Black (or Gone)?

For each ball i, its history is characterized by the interval of time (Xi,Yi) that it spends in the White state. It is Black before that, and Gone afterwards. The times at which all balls are Black or Gone are the times outside the union of these intervals (Xi,Yi). They're all Gone at times that are after the union of these intervals. So an equivalent formulation of the question is:

Q: What's the probability f(a,b) that the union of the intervals (Xi,Yi) is contiguous?

This formulation mostly agrees with the original one, except that it gives a different value for the case a=0. Because we said "contiguous" rather than "contiguous and includes 0", we have f(0,b)=f(1,b1) rather than f(0,b)=0. So in this formulation we're interested in showing that f(0,b)1 as b.

We might hope that there are values ε,M depending on b for which, with high probability:

  • (A) Each (Xi,Yi) intersects (ε,M).
  • (B) The union of (Xi,Yi) covers (ε,M).

Roughly, for (A) we need ε=b1/2o(1), and M>logb+ω(1). Guaranteeing (B) is a bit tricky. One might hope some interval just covers (ε,M) with high probability, but AFAIK that's too ambitious. What we can do instead is find a third parameter C for which, with high probability

  • (A) Each (Xi,Yi) intersects (ε,M).
  • (B1) Some (Xi,Yi) covers (ε,C), and
  • (B2) Some (Xi,Yi) covers (C,M).

A bit of experimentation gives values that work:

ε=b(1/2+α)C=log(b1/2αγ)=(1/2αγ)logbM=log(blogb)=logb+1/2loglogb,

where α>0, γ>0, and α+γ<1/2.

At this point it's a computation.

(A) holds with high probability:

Note that Xi and Zi=YiXi are independent and exponentially distributed, so the joint distribution of (Xi,Yi) has density ϕ(x,y)=exp(x)exp((yx))10<x<y=exp(y)10<x<y.

The probability that some (Xi,Yi) lies entirely to the left of (ε,M) is at most

bP(Yi<ε)=bε0εxexp(y) dy dx=bO(ϵ2)=O(b2α)=o(1).

The probability that some (Xi,Yi) lies entirely to the right of (ε,M) is at most

bP(Xi<M)=bMxexp(y) dy dx=bexp(M)=1/logb=o(1).

So each (Xi,Yi) intersects (ε,M) with probability 1o(1).

(B2) holds with high probability:

For a fixed i, the probability that (Xi,Yi) covers (C,M) is

p=P(Xi<C,Yi>M)=C0Mexp(y) dy dx=Cexp(M)

Plugging in our values, this is

p=Cexp(M)=(1/2αγ)(logb)b1(logb)1/2=b1(1/2αγ)logb=b1ω(1)

(Here ω(1) denotes a term that goes to infinity as b.) So the probability that none of the (Xi,Yi) cover (C,M) is

(1p)b=(1ω(1)/b)b<exp(ω(1))=o(1),

so one of those intervals covers (C,M) with probability 1o(1).

(B1) holds with high probability:

As above, for a fixed i, the probability that (Xi,Yi) covers (ε,C) is

εexp(C)=b(1/2+α)b1/2+α+γ=b1bγ=b1ω(1)

So one of those intervals covers (ε,C) with probability 1o(1).

In other words, with high probability:

  • No ball turns White and disappears before ε
  • Some ball turns White by time ε and survives until time C.
  • Some ball turns White by time C and and survives until time M.
  • No ball turns White after time M (i.e. no balls are Black at time M.)

It follows that with high probability, there is no point after the first ball turns White that all the surviving balls are Black.

3
  • I also suspect there's a less-tedious argument in the continuous-time independent-balls formulation. (E.g. something in terms of an explicit formula for the distribution of the ball-states at time t, which can be handled with matrix exponentials?) Alas I haven't the time to look for a shorter answer. Commented Jan 18 at 1:10
  • Follow-up question: characterize which joint distributions of X,Y have the property that sampling the distribution n times and taking the union of the intervals (Xi,Yi) results in a contiguous interval with high probability as n. Are there any nondegenerate cases where this isn't true? Commented Jan 18 at 1:44
  • If I'm not mistaken, looking at M=logb+loglogb and computing the probability that exactly one interval is stranded after M gives you a bound f(0,b)<1(logb)1+o(1), so the probability goes to 1 fairly slowly. Commented Jan 18 at 6:14
5

The following answer is incomplete.

Clearly, 0f1. Let h:=1f, so that 0h1, h(a,0)=0, and h(0,b)=1 if b1. Here and in what follows, a and b are nonnegative integers.

We want to show that h(1,n)0 (as n). The idea is to construct a suitable majorant g of h.

Let g(a,b):=2(1+a)b2(1+a)b+a(1+a+blnb) if b>0, with g(a,0):=0. It is enough to show that h(a,b)g(a,b) for all a,b.

Let us do this by induction on m:=m(a,b):=a+2b. If m=0, then (1) is trivial. Also, (1) turns into an equality if a=0 or b=0. If now a1 and b1, then (1) follows by induction from the given recurrence for f (and the same recurrence for h) and the inequality g(a,b)aa+bg(a1,b)+ba+bg(a+1,b1) for a,b1. (To use the induction, note that m(a1,b)=m(a+1,b1)=a+2b1<m(a,b).)


Remark: Inequality (2) actually fails to hold, by a small amount of 1013 for some very large a,b. I am leaving this answer for now, hoping that someone can modify g a bit to make (2) hold.

2
  • 2
    Nice idea! However, I felt a bit lied to, with only the Remark at the end indicating you don't yet have a proof. I edited (as I see) appropriately. Commented Dec 11, 2023 at 15:44
  • 2
    @mathworker21 : Sorry if you "felt a bit lied to". That was not my intention. As soon as I discovered the mistake, I added the Remark, in boldface. That the remark is at the end of the answer is chronological. However, your edit is warranted and is now accepted. Commented Dec 11, 2023 at 15:56
4
+50

Reduction:

Fix p(0,1/2). For large n, it is not hard to see that f(1,n)>f((p4p2)n,n)(13p).

Indeed, consider the balls an urn's setup of Fedor Petrov. For the first pn steps, we have at most pn white balls and at least (1p)n total balls, so we expect to eat at most p1ppn<(2ϵ)p2n white balls total (where ϵ>0 since p<1/2). By a Chernoff bound, a.a.s. we should eat at most 2p2n balls in the first pn steps, and (assuming we run all these steps), we end up creating at least (p2p2)n white balls.

Meanwhile, the probability that the original white ball is eaten in the first pn steps is at most (pn)1(1p)n2p. For large n, the a.a.s. event fails with probability at most p, thus a union bound gives that with probability 13p, that at time pn we have (p4p2)n white balls and n black balls.

Finishing touches:

It remains to show that for fixed c>0 that f(cn,n)=1o(1). This follows from two observations (thanks to Fedor Petrov in the comments for clarifying my previous hand-wavy argument rigorous).

Lemma 1: f(a,b)a/(a+b) for all a,b.

Proof: This can either easily be deduced from the original functional definition of f, or otherwise can be derived from the probabilistic interpretation. Indeed, f(a,b) is at least the probability that when we order all a+b current balls according to what time they are drawn from the jar (which is distributed like a random permutation), that the last ball is white (since then all black balls are recolored before the white balls are consumed). QED.

Lemma 2: Fix an open interval E[0,1]. There exists some ϵ,δ>0 so that for all pE, we have that f((1p)n,pn)f((1p)(1ϵ)n+δnn2/3,p(1ϵ)n+n2/3)o(1) (with the error term tending to zero as n, uniformly in all choices p.

Proof: We shall determine ϵ,δ a bit later.

We keep on taking steps until we have picked out ϵn balls which were originally in the jar. By a Chernoff bound, asymptotically almost surely we eat at most (1p)ϵn+n2/3 of the original white balls, and recolor at least pϵnn2/3 of the original black balls. Also, assuming that ϵp/3 we deterministically always have (2/3)pn original black balls (which haven't been recolored) and (1/3)pn new white balls.

So (via more Chernoff bounds and some coupling), almost surely we eat <(1/2+.0001)pϵ of our new white balls (since at each step we are at least twice as likely to recolor a black ball then eat a new white ball). Thus, we may take ϵ=min. QED

Now fix some small \eta>0. By the original reduction, we have that f(1,n)> f((\eta-4\eta^2)n,n))(1-3\eta)\ge f(\eta/2n,n)-3\eta assuming \eta is small (recall f(a,b)\le 1 uniformly). To finish, we now claim that f((\eta/2)n,n)> 1-2\eta for all large n (whence f(1,n) > 1-5\eta for all large n, so slowly having \eta\downarrow 0 gives f(1,n)>1-o(1)).

To verify this claim, we first note that f((1-\eta)n',\eta n')\ge 1-\eta uniformly (by Lemma 1). Then we take \epsilon, \delta from Lemma 2 applied to the interval E = ((\eta/2)/(1+\eta/2),1-\eta), and note that the function \phi:p\mapsto \frac{(1-p)(1-\epsilon)+\delta}{p(1-\epsilon)} -\frac{1-p}{p} is continuous and non-negative on (0,1), thus there is some c_0>0 so that \phi(p)>c_0 for all p\in E (we can take c_0:= \delta/\epsilon\max(E)). So, applying Lemma 2 a bunch of times (\approx 1/c_0\eta), we should be able to iteratively increment the ratio (1-p)/p to find some n' so that f((\eta/2)n, n)\ge f((1-\eta)n',n')-\eta. This completes the proof.

\endgroup
14
  • 1
    \begingroup We have a uniform bound f(a, b) \ge a/(a+b) . For getting at least 99 percent of white balls we may partition the steps onto billion parts and apply Chernoff bound for each part, can not we? \endgroup Commented Dec 11, 2023 at 20:46
  • 1
    \begingroup In your first display, p cannot exceed 1/4, because in that case p-4p^2 is negative. \endgroup
    – GH from MO
    Commented Dec 12, 2023 at 2:24
  • 2
    \begingroup @ZachHunter then I suggest to rewrite the answer, as now it looks like incomplete, and my MO experience says that nobody reads the comments \endgroup Commented Dec 17, 2023 at 6:58
  • 2
    \begingroup yeah I will rewrite in a day or so. \endgroup Commented Dec 17, 2023 at 11:42
  • 2
    \begingroup @ZachHunter Are you going to rewrite your answer? \endgroup Commented Jan 18 at 2:46
3
\begingroup

This can be solved using the so-called "fluid limit" for stochastic processes.

Consider B_k, W_k the number of black (resp. white) balls at time k. Our aim is to obtain a macroscopic behaviour for these processes, in the limit n \to +\infty. For this, note that:

\begin{align} \mathbb{E}[B_{k+1} - B_k | \mathcal{F}_k] &= \dfrac{-B_k}{B_k + W_k} \\ \mathbb{E}[W_{k+1} - W_k | \mathcal{F}_k] &= \dfrac{B_k - W_k}{B_k + W_k} \end{align}

In the same way that a biased random walk converges to a straight line at large scales, we can hope that this process has some deterministic limit once it is adequately rescaled. Indeed, this is the case: as n \to +\infty, uniformly over t \in [0, 2 - \varepsilon] for any \varepsilon > 0,

(b_n(t), w_n(t)) =(\frac{B_{[nt]}}{n}, \frac{W_{[nt]}}{n}) \overset{\mathbb{P}, \|\cdot\|_{\infty}}{\longrightarrow} (b, w)

where

b' = \dfrac{-b}{b+w}, w' = \dfrac{b-w}{b + w}

and with initial conditions b(0) = 1, w(0) = 0.

Let us assume this result for now. Some elementary analysis shows that b and w both fall back down to 0 at t=2, with b'(2) = 0 and w'(2) = -1. As a result, if K > 0 is large, we may pick \varepsilon such that \frac{w(2 - \varepsilon)}{b(2 - \varepsilon)} > K: then, for large enough n, \frac{W_{[n(2-\varepsilon)]}}{B_{[n(2 - \varepsilon)]}} > \frac{K}{2} w.h.p. It is then relatively clear that, with overwhelming probability, B reaches 0 before W from this point, giving us the desired result.

We now just need to prove our functional convergence. We can start by decomposing B_k into its predictable and martingale components:

B_k = \sum_{l=0}^{k-1} \frac{-B_l}{B_l + W_l} + M_k

However, M_k is quite small! Indeed, |M_k - M_{k-1}| \leq 1, so \mathbb{E}[M_n^2] \leq n and, by Doob's maximal inequality, \displaystyle\max_{0 \leq k \leq n} |M_k| \leq C_\eta \sqrt{n}) with probability at least 1-\eta. Thus, if 0 \leq t < 2 , with probability \geq 1-\eta,

b_n(t) = \int_0^t \frac{-b_n(s)}{b_n(s) + w_n(s)} ds +\frac{C_\eta}{\sqrt{n}}

and so

|b_n(t) - b(t)| \leq \frac{C_\eta}{\sqrt{n}} + \int_0^t \frac{b(s)}{b(s) + w(s)} - \frac{b_n(s)}{b_n(s) + w_n(s)} ds

However, we can also see that 2b(s) + w(s) = 2-s (by taking the derivative) and 2 b_n(s) + w_n(s) = 2 - s + O(\frac{1}{n}) (by recursion over s = \frac{k}{n}). As a result,

|b_n(t) - b(t)| \leq \frac{C_\eta}{\sqrt{n}} + \int_0^t \frac{|b_n(s) - b(s)|}{1-\frac{s}{2}} ds

Similarly, with probability \geq 1-\eta,

|w_n(t) - w(t)| \leq \frac{C_\eta}{\sqrt{n}} + \int_0^t 2\frac{|w_n(s) - w(s)|}{1-\frac{s}{2}} ds

By Gronwall's lemma, we therefore obtain that w.h.p.

|b_n(t) - b(t)| \leq \frac{C_\eta}{\sqrt{n}(2-t)^2}; |w_n(t) - w(t)| \leq \frac{C_\eta}{\sqrt{n}(2-t)^4}

showing that (b_n, w_n) \overset{\mathbb{P}}{\longrightarrow} (b, w), uniformly over [0, 2-\varepsilon] for any given \varepsilon.

Edit: a few extra points:

  • the proof as i wrote it is not actually complete, since I did not prove that w_n(t) did not hit 0 for t close to 0. However, it is easy to see that w.h.p W_k > 0 for 0 < k < \varepsilon n, which is sufficient: Gronwall's inequality then says that W_k > 0 for \varepsilon n < k < (2 - \varepsilon) n.

  • since b_n is decreasing, the convergence is actually uniform over [0, 2].

\endgroup
2
\begingroup

I will use the probabilistic interpretation in my proof.

First, note that P(1, n-1) = P(0,n) so we can reformulate the problem as follows:

"We start with a hat with n black balls. When we take out a black ball, we paint it white and return it. When we take out a white ball, we leave it outside. We stop when we have only one ball in the hat. What is the probability that it is white?"

One issue with this formulation is that the process can take either 2n-2 or 2n-1 steps, so we will instead continue until there are no balls in the hat left, which will always take 2n steps. In this interpretation, the last ball is black if it was pulled twice in the last two steps.

If we label the balls as b_1, \cdots, b_n, all the possible outcomes are described by words of length 2n in which all b_is appear twice. All these outcomes are equally likely, so we can find 1-P(0,n) as follows:

There are f_n=\frac{(2n)!}{2^n} outcomes in total. Out of these, there are precisely nf_{n-1} outcomes which have end in b_ib_i for some i. This means that 1-P(0,n)=nf_{n-1}/f_n=\frac{1}{2n-1}\implies\\ \implies P(1,n)=P(0,n+1)=1-\frac{1}{2n+1}\xrightarrow{n\to\infty}1

Update: thanks to the comments, I have realised that I was solving the problem with a different boundary condition. Even then, this solution is actually wrong, because individual outcomes aren't equally likely.

\endgroup
1
  • 2
    \begingroup No, we stop when they all become of the same color \endgroup Commented Jan 17 at 16:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .