Return to Answer

I believe I have a "moral solution". The final paragraph must be made rigorous (or perhaps there is a cleaner way to finish things off), but it looks like this is the right direction:

Reduction:

Finishing touches (hand-wavy):

It remains to show that for fixed $c>0$ that $f(cn,n)=1-o(1)$. I will sketch an approach which I believe could made rigorous.

Let's renormalize this as $f(pn,qn)$ where $p+q= 1$. If we run this for $t =\epsilon n$ steps, then another Chernoff bound says we should almost surely have $\approx ((1-\epsilon)p+\epsilon q)n$ white balls and $\approx (1-\epsilon)q n$ black balls (up to $O(\epsilon^2)$ errors). But if one looks at the function $$\frac{(1-x-100x^2)p+(x-100x^2)q}{(1-x+100x^2)q}-\frac{p}{q}$$for any $p,q\in (0,1)$ satisfying $p+q=1$ (on Desmos, say), it is clear that that $x=0$ is not a local maximum.

Thus for small $\epsilon$, we should get that $f(pn,qn)\ge f(p'n',q'n')-o(1)$ for $p'>p$ and $n'\ge n/2$. And so presumably as we iterate things (replacing $p'$ by $p''$ and so on), we'll get that $f(pn,qn)\ge f((1-\delta)n^*,\delta n^*)-o(1)$ where $n^* = \Omega_{p,\delta}(n)$. From here, we can use the observation (thanks to Fedor Petrov) that $f(a,b)\ge a/(a+b)$ to finish things (to see why this is true, order the balls according to the time in which they are first removed from the jar; we have that this is a random permutation, and if the last ball in the ordering is white, then we will end with all balls white).

Reduction:

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.

I believe I have a "moral solution". The final paragraph must be made rigorous (or perhaps there is a cleaner way to finish things off), but it looks like this is the right direction:

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 (hand-wavy):

It remains to show that for fixed $c>0$ that $f(cn,n)=1-o(1)$. I will sketch an approach which I believe could made rigorous.

Let's renormalize this as $f(pn,qn)$ where $p+q= 1$. If we run this for $t =\epsilon n$ steps, then another Chernoff bound says we should almost surely have $\approx ((1-\epsilon)p+\epsilon q)n$ white balls and $\approx (1-\epsilon)q n$ black balls (up to $O(\epsilon^2)$ errors). But if one looks at the function $$\frac{(1-x-100x^2)p+(x-100x^2)q}{(1-x+100x^2)q}-\frac{p}{q}$$for any $p,q\in (0,1)$ satisfying $p+q=1$ (on Desmos, say), it is clear that that $x=0$ is not a local maximum.

Thus for small $\epsilon$, we should get that $f(pn,qn)\ge f(p'n',q'n')-o(1)$ for $p'>p$ and $n'\ge n/2$. And so presumably as we iterate things (replacing $p'$ by $p''$ and so on), we'll get that $f(pn,qn)\ge f((1-\delta)n^*,\delta n^*)-o(1)$ where $n^* = \Omega_{p,\delta}(n)$.

I believe I have a "moral solution". The final paragraph must be made rigorous (or perhaps there is a cleaner way to finish things off), but it looks like this is the right direction:

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 (hand-wavy):

It remains to show that for fixed $c>0$ that $f(cn,n)=1-o(1)$. I will sketch an approach which I believe could made rigorous.

Let's renormalize this as $f(pn,qn)$ where $p+q= 1$. If we run this for $t =\epsilon n$ steps, then another Chernoff bound says we should almost surely have $\approx ((1-\epsilon)p+\epsilon q)n$ white balls and $\approx (1-\epsilon)q n$ black balls (up to $O(\epsilon^2)$ errors). But if one looks at the function $$\frac{(1-x-100x^2)p+(x-100x^2)q}{(1-x+100x^2)q}-\frac{p}{q}$$for any $p,q\in (0,1)$ satisfying $p+q=1$ (on Desmos, say), it is clear that that $x=0$ is not a local maximum.

Thus for small $\epsilon$, we should get that $f(pn,qn)\ge f(p'n',q'n')-o(1)$ for $p'>p$ and $n'\ge n/2$. And so presumably as we iterate things (replacing $p'$ by $p''$ and so on), we'll get that $f(pn,qn)\ge f((1-\delta)n^*,\delta n^*)-o(1)$ where $n^* = \Omega_{p,\delta}(n)$. From here, we can use the observation (thanks to Fedor Petrov) that $f(a,b)\ge a/(a+b)$ to finish things (to see why this is true, order the balls according to the time in which they are first removed from the jar; we have that this is a random permutation, and if the last ball in the ordering is white, then we will end with all balls white).

I believe I have a "moral solution". The final paragraph must be made rigorous (or perhaps there is a cleaner way to finish things off), but it looks like this is the right direction:

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 (hand-wavy):

It remains to show that for fixed $c>0$ that $f(cn,n)=1-o(1)$. I will sketch an approach which I believe could made rigorous.

Let's renormalize this as $f(pn,qn)$ where $p+q= 1$. If we run this for $t =\epsilon n$ steps, then another Chernoff bound says we should almost surely have $\approx ((1-\epsilon)p+\epsilon q)n$ white balls and $\approx (1-\epsilon)q n$ black balls (up to $O(\epsilon^2)$ errors). But if one looks at the function $$\frac{(1-x-100x^2)p+(x-100x^2)q}{(1-x+100x^2)q}-\frac{p}{q}$$for any $p,q\in (0,1)$ satisfying $p+q=1$ (on Desmos, say), it is clear that that $x=0$ is not a local maximum.

Thus for small $\epsilon$, we should get that $f(pn,qn)\ge f(p'n',q'n')-o(1)$ for $p'>p$ and $n'\ge n/2$. And so presumably as we iterate things (replacing $p'$ by $p''$ and so on), we'll get that $f(pn,qn)\ge f((1-\delta)n^*,\delta n^*)-o(1)$ where $n^* = \Omega_{p,\delta}(n)$. From here, (I assume) standard balls and urns or some first moment argument should give that $f((1-\delta)n^*,\delta n^*) \le c_\delta +o(1)$ where $c_\delta \to 0$ as $\delta \to 0$.

I believe I have a "moral solution". The final paragraph must be made rigorous (or perhaps there is a cleaner way to finish things off), but it looks like this is the right direction:

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 (hand-wavy):

It remains to show that for fixed $c>0$ that $f(cn,n)=1-o(1)$. I will sketch an approach which I believe could made rigorous.

Let's renormalize this as $f(pn,qn)$ where $p+q= 1$. If we run this for $t =\epsilon n$ steps, then another Chernoff bound says we should almost surely have $\approx ((1-\epsilon)p+\epsilon q)n$ white balls and $\approx (1-\epsilon)q n$ black balls (up to $O(\epsilon^2)$ errors). But if one looks at the function $$\frac{(1-x-100x^2)p+(x-100x^2)q}{(1-x+100x^2)q}-\frac{p}{q}$$for any $p,q\in (0,1)$ satisfying $p+q=1$ (on Desmos, say), it is clear that that $x=0$ is not a local maximum.

Thus for small $\epsilon$, we should get that $f(pn,qn)\ge f(p'n',q'n')-o(1)$ for $p'>p$ and $n'\ge n/2$. And so presumably as we iterate things (replacing $p'$ by $p''$ and so on), we'll get that $f(pn,qn)\ge f((1-\delta)n^*,\delta n^*)-o(1)$ where $n^* = \Omega_{p,\delta}(n)$.