Giving a general term of a recursive function, and upper bound for it

Question

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 )

Answer 1

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.