A strange sampling/convergence problem

48 Views Asked by At

The following problem appeared in the analysis of an online learning algorithm, and so far I couldn't reach to any significant result.

Any help is much appreciated.

We are given a real sequence $l_1,l_2,\ldots$ where each element $l_i$ is chosen from the unit interval and a constant $\epsilon$ such that $\limsup_T \frac{1}{T}\sum_{t=1}^Tl_t < \epsilon - c$ for a positive constant $c$.

Finally we play the following game:

  1. Start with a $p_1\in(0,1)$, and $s = 0$.
  2. At each round $t$:

    2.1. Choose a random integer $X \sim\mathrm{Geometric}\left(1-p_t\right)$ (i.e. $E[X] = 1/(1-p_t)$)

    2.2. Update $s = s+X$

    2.3. Update $p_{t+1} = p_t ~ e^{ l_s - \epsilon}$

The question we are interested is the limit of $p_t$ (if it exists) and if the partial sum $\sum_{t=1}^T p_t$ converges or diverges to infinity?