Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 )
share|improve this question
Your question (2) is a real question; but for the life of my I can't see how you didn't answer question (1) even before you asked it. –  Greg Martin Apr 18 '13 at 20:35
@Greg Martin, I see for question (1), I'll remove it since it is very simple, you're rihjt. However, what about the question (2), i.e., the upper bound ? –  shna Apr 19 '13 at 8:35

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.