Let a constant $B \ge 1$, and let $l\_1 = 0$, $b\_1 = 0$ be the values of $l$ and $b$ (respectively) at time $t = 1$.


Let $l\_{t+1} = l\_t + 1$ if $b\_i < B$, and $l\_{t+1} = l\_t$ otherwise


Let $b\_{t+1} = b\_t + \frac{l\_{t+1}}{t}$


So here I can intuitively see that $\forall t \le B: l\_t = b\_t = t$, and that $\forall t > B: l\_t = B$. So $\forall t: l\_t \le B$ (i.e. $l$ is bounded above by $B$).


I have two questions:


Can we also give an upper bound on $l\_t$ if it was defined as: Let $l\_{t+1} = l\_t + 1$ if $b\_i < B$ and with probability $p\_t$, and $l\_{t+1} = l\_t$ otherwise. That is with a probability $p\_t$ the value of l is increased if $b\_i < B$.


Note: Here is the simple algorithm corresponding to these functions to better explain the problem.



```
let b=0, l=0, T=0.7, N=100
for t from 1 to N:
   get the observation x_t
   let P(x_t) the probability associated with the random variable x_t
   if P(x_t) > T and b < B then l := l + 1
   b := b + ( l / t )

```


Giving a general term of a recursive function, and upper bound for it
There's no general upper bound. 


Suppose $p\_t<1$ for every $t$ and $\sum\_{t=1}^\infty p\_t = \infty$. 
For every $N$ there's a positive probability that $l\_N = 0$, then $l\_t$ will be larger than $NB$ eventually.


You can get a very basic probabalistic bound using Markov's inequality


First let $\tilde l\_t$ and $\tilde b\_t$ be sequences of random variables with the same definition as $l\_t$ and $b\_t$ but setting $B=\infty$


Then we have $\mathbb E\left( \tilde l\_t\right)$ $\sum\_{i=0}^t$ $p\_t$ and 
$\mathbb E(\tilde b\_t) = \sum\_{i=0}^t \frac{\mathbb E(\tilde l\_t)}t$


But $b\_t$ is bounded above by $t$ so by Markov's inequality
$\mathbb P(b'\_t < B) =\mathbb P(t-b'\_t>t-B) \leq \frac{t-\mathbb E(b'\_t) }{t-B}$


Then we have $\mathbb E(l\_t)\leq\sum\_{i=0}^t p\_t \frac{t-\mathbb E(b'\_t) }{t-B}$.
If $p\_t$ is summable you 'll get a limit as $t\to\infty$.


The Markov inequality bound for $\mathbb P(b'\_t < B)$ is a pretty blunt instrument
if you notice that you can express
'$$b\_t = \sum\_{s=1}^t X\_t \sum\_{i=s}^t \frac 1s $$'
where '$X\_t$' are independent Bernoulli '$p\_t$' random variables, you might be able to get a Chernoff bound which would be better. 


