How to show a function converges to 1

Question

Consider the following recurrence relation in two variables: $$f(a, b) = \frac{a}{a+b} f(a-1,b)+ \frac{b}{a+b}f(a+1,b-1) $$ 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 $a\ge0$.

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.

Answer 1

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, $\lambda = 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 $(X_i, Y_i)$ 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 $(X_i, Y_i)$. 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 $(X_i, Y_i)$ 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, b-1)$ rather than $f(0, b) = 0$. So in this formulation we're interested in showing that $f(0, b) \to 1$ as $b \to \infty$.

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

• (A) Each $(X_i, Y_i)$ intersects $(\varepsilon, M)$.
• (B) The union of $(X_i, Y_i)$ covers $(\varepsilon, M)$.

Roughly, for (A) we need $\varepsilon = b^{1/2} o(1)$, and $M > \log b + \omega(1)$. Guaranteeing (B) is a bit tricky. One might hope some interval just covers $(\varepsilon, 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 $(X_i, Y_i)$ intersects $(\varepsilon, M)$.
• (B1) Some $(X_i, Y_i)$ covers $(\varepsilon, C)$, and
• (B2) Some $(X_i, Y_i)$ covers $(C, M)$.

A bit of experimentation gives values that work:

\begin{align*} \varepsilon &= b^{-(1/2+\alpha)} \\ C &= \log(b^{1/2 - \alpha - \gamma}) = (1/2 - \alpha - \gamma) \log b \\ M &= \log(b \sqrt{\log b}) = \log b + 1/2 \log \log b, \end{align*}

where $\alpha > 0$, $\gamma > 0$, and $\alpha + \gamma < 1/2.$

At this point it's a computation.

(A) holds with high probability:

Note that $X_i$ and $Z_i = Y_i - X_i$ are independent and exponentially distributed, so the joint distribution of $(X_i, Y_i)$ has density $$\phi(x,y) = \exp(-x)\exp(-(y-x)) \mathbf1_{0 < x < y} = \exp(-y) \mathbf1_{0 < x < y}.$$

The probability that some $(X_i, Y_i)$ lies entirely to the left of $(\varepsilon, M)$ is at most

$$ b \,\mathbf P(Y_i <\varepsilon) = b \int_0^\varepsilon \int_x^\varepsilon \exp(-y)\ dy\ dx = b O(\epsilon^2) = O(b^{-2\alpha}) = o(1). $$

The probability that some $(X_i, Y_i)$ lies entirely to the right of $(\varepsilon, M)$ is at most

$$ b \,\mathbf P(X_i < M) = b \int_M^\infty \int_x^\infty \exp(-y) \ dy\ dx = b \exp(-M) = 1/\sqrt{\log b} = o(1). $$

So each $(X_i, Y_i)$ intersects $(\varepsilon, M)$ with probability $1 - o(1).$

(B2) holds with high probability:

For a fixed $i$, the probability that $(X_i,Y_i)$ covers $(C, M)$ is

$$ p = \mathbf P(X_i < C, Y_i > M) = \int_0^C\int_M^\infty \exp(-y) \ dy\ dx = C\exp(-M) $$

Plugging in our values, this is

\begin{align*} p = C\exp(-M) &= (1/2 - \alpha - \gamma) (\log b) b^{-1} (\log b)^{-1/2} \\ &= b^{-1}(1/2 - \alpha - \gamma) \sqrt{\log b} \\ &= b^{-1} \omega(1) \end{align*}

(Here $\omega(1)$ denotes a term that goes to infinity as $b \to \infty$.) So the probability that none of the $(X_i, Y_i)$ cover $(C, M)$ is

$$ (1-p)^b = (1-\omega(1)/b)^b < \exp(-\omega(1)) = o(1), $$

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

(B1) holds with high probability:

As above, for a fixed $i$, the probability that $(X_i,Y_i)$ covers $(\varepsilon, C)$ is

\begin{align*} \varepsilon \exp(-C) &= b^{-(1/2+\alpha)} b^{-1/2+\alpha+\gamma} = b^{-1} b^{\gamma} = b^{-1} \omega(1) \end{align*}

So one of those intervals covers $(\varepsilon, C)$ with probability $1-o(1)$.

In other words, with high probability:

• No ball turns White and disappears before $\varepsilon$
• Some ball turns White by time $\varepsilon$ 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.

Answer 2

The following answer is incomplete.

Clearly, $0\le f\le1$. Let $h:=1-f$, so that $0\le h\le1$, $h(a,0)=0$, and $h(0,b)=1$ if $b\ge1$. Here and in what follows, $a$ and $b$ are nonnegative integers.

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

Let $$g(a,b):=\frac{2 (1+a) b}{2 (1+a) b+a (1+a+b \ln b)}$$ if $b>0$, with $g(a,0):=0$. It is enough to show that $$h(a,b)\le g(a,b) \tag{1}\label{1}$$ for all $a,b$.

Let us do this by induction on $m:=m(a,b):=a+2b$. If $m=0$, then \eqref{1} is trivial. Also, \eqref{1} turns into an equality if $a=0$ or $b=0$. If now $a\ge1$ and $b\ge1$, then \eqref{1} follows by induction from the given recurrence for $f$ (and the same recurrence for $h$) and the inequality $$g(a,b)\ge\frac a{a+b}\, g(a-1,b)+ \frac b{a+b}\,g(a+1,b-1) \tag{2}\label{2} $$ for $a,b\ge1$. (To use the induction, note that $m(a-1,b)=m(a+1,b-1)=a+2b-1<m(a,b)$.)

---

Remark: Inequality \eqref{2} actually fails to hold, by a small amount of $\asymp10^{-13}$ for some very large $a,b$. I am leaving this answer for now, hoping that someone can modify $g$ a bit to make \eqref{2} hold.

Answer 3

Reduction:

Fix $p\in (0,1/2)$. For large $n$, it is not hard to see that $$f(1,n)>f((p-4p^2) n,n)(1-3p).$$

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 $(1-p)n$ total balls, so we expect to eat at most $\frac{p}{1-p}pn<(2-\epsilon)p^2n$ white balls total (where $\epsilon>0$ since $p<1/2$). By a Chernoff bound, a.a.s. we should eat at most $2p^2n$ balls in the first $pn$ steps, and (assuming we run all these steps), we end up creating at least $(p-2p^2)n$ white balls.

Meanwhile, the probability that the original white ball is eaten in the first $pn$ steps is at most $(pn)\frac{1}{(1-p)n}\le 2p$. For large $n$, the a.a.s. event fails with probability at most $p$, thus a union bound gives that with probability $\ge 1-3p$, that at time $pn$ we have $\ge (p-4p^2)n$ white balls and $\le n$ black balls.

Finishing touches:

It remains to show that for fixed $c>0$ that $f(cn,n)=1-o(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)\ge 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\subset [0,1]$. There exists some $\epsilon,\delta>0$ so that for all $p \in E$, we have that $f((1-p)n,pn) \ge f((1-p)(1-\epsilon)n+\delta n-n^{2/3},p(1-\epsilon)n+n^{2/3})-o(1)$ (with the error term tending to zero as $n\to \infty$, uniformly in all choices $p$.

Proof: We shall determine $\epsilon,\delta$ a bit later.

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

So (via more Chernoff bounds and some coupling), almost surely we eat $<(1/2+.0001)p\epsilon$ 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 $\epsilon = \min(E)/3, \delta = .4999\epsilon \min(E)$. 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.

Answer 4

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

Answer 5

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