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?
Best Answer
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.