# Upper bound on $x_{i+1} = x_i (1-(1-\frac{1}{n})^{x_{i}-1})$ with $x_0=n$

inequality

I am trying to upper bound the convergence speed of $$x_{i+1} = x_i (1-(1-\frac{1}{n})^{x_{i}-1})$$ with $$x_0=n$$ to below $$1$$. I can get a "trivial" upper bound using

$$x_{i+1} = x_i (1-(1-\frac{1}{n})^{x_{i}-1}) \leq x_i(1-\frac{1}{e}) \leq … \leq (1-\frac{1}{e})^in \implies x_{\lceil \frac{\log n}{\log (1+\frac{1}{e})} \rceil} \leq 1$$.

However, I am trying to get a tighter upper bound. Some experiments show that $$x_i$$ converges to $$1$$ extremely quickly (much faster than $$O(\log n)$$. Any ideas?

I was finally able to solve the problem myself. Here is a proof that the recurrence converges to $$1$$ in $$\Theta(\log \log n)$$ iterations.

We use Bernoulli inequality to get:

$$x_{i+1}=x_i(1-(1-\frac{1}{n})^{x_i-1}) \leq x_i(1-(1-\frac{x_i-1}{n}))\leq \frac{x_i^2}{n}$$

Let $$T=\lceil \log \log n \rceil$$. Then using bound $$1$$: $$x_T \leq (1-\frac{1}{e})^{\lceil \log \log n \rceil}n \leq n^{1-\frac{\left(1-\log(e-1) \right) \cdot \log \log n}{\log n}}$$

So after $$T$$ iterations, $$x_T\leq n^{1-\frac{\left(1-\log(e-1) \right) \cdot \log \log n}{\log n}}$$. Now we use the second bound. In the $$T+1$$ iteration, we get: $$x_{T+1}\leq \frac{n^{2(1-\frac{\left(1-\log(e-1) \right) \cdot \log \log n}{\log n})}}{n} = n^{1-\frac{2\left(1-\log(e-1) \right) \cdot \log \log n}{\log n}}$$ In the $$T+2$$ iteration: $$x_{T+2}\leq n^{1-\frac{4\left(1-\log(e-1) \right) \cdot \log \log n}{\log n}}$$ So after an additional $$T'=\lceil \log_2 \left( \frac{\log n}{(1-\log(e-1))\log \log n} \right) \rceil$$ iterations, we get that $$x_{T+T'+1} \leq 1$$ In total we get a total time of $$\lceil \log \log n \rceil + \lceil \log_2 \left( \frac{\log n}{(1-\log(e-1))\log \log n} \right) \rceil$$ This is $$O(\log \log n)$$.

Now we prove a matching lower bound. Note that $$(1-(1-\frac{1}{n})^{x_i-1}) \geq 1-e^{-\frac{x_i-1}{n}}$$ So we have that $$x_{i+1} = x_i(1-(1-\frac{1}{n})^{x_i-1}) \geq x_i (1-e^{-\frac{x_i-1}{n}})$$ However, we have that $$x_i (1-e^{-\frac{x_i-1}{n}}) \geq \frac{x_i^2}{2n}$$ This follows because of the inequality for $$x\leq 1/2$$: $$1-e^{-2x}\geq x$$ And since $$\frac{x_i-1}{n}\leq 1$$, then we get the following inequality: $$x_{i+1} \geq \frac{x_i^2}{2n}$$ Iterating the recurrence, we get: $$x_{i} \geq \frac{n^{2^i}}{(2n)^{1+2+4+..+2^{i-1}}} = \frac{n^{2^i}}{(2n)^{2^i-1}} = \frac{n}{2^{2^i-1}}$$ So after $$\log_2 \log _2 n - 10$$ iterations, we still have $$x_i> 1$$ so we need at least $$\Omega(\log \log n)$$ rounds.