Upper bound on $x_{i+1} = x_i (1-(1-\frac{1}{n})^{x_{i}-1})$ with $x_0=n$ 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?
 A: 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.
