Consider the stochastic process $X: \mathbb{N} \rightarrow \mathbb{N}$ defined as follows:
$$\left\{ \begin{array}{ll} X_1 = 0\\ X_{n + 1} = X_n + \mathbf{1}_{\{z_n \leq P_n\}}\\ P_n = (X_n + n) / (M + n) \end{array} \right.$$ where $\left(z_n\right)_{n\in\mathbb{N}}$ is a sequence of i.i.d. r.v. uniformly distributed over $\left[0, 1\right]$ and $M \in \mathbb{N}^*$ is constant.
Define the stopping time $\tau = \inf \left\{j > 0 \,|\, X_j = M \right\}$. Then I want to prove that $\mathbb{E}\left[\tau\right] \geq 2M$.
This problem emerges from the analysis of the algorithm "Snow Plow" defined here by Paolo Ferragina, who unfortunately provides a faulty analysis.