Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

My question is related the hitting time of not a random walk, but a more general martingale process.

Suppose we start with an arbitrary $x_0=x$ with $0\leq x\leq 1$. We compute $x_{t+1}$ from $x_t$ as follows:

\begin{equation} x_{t+1}= \begin{cases} x_t + \epsilon_t & \textrm{with probability $\frac{\epsilon'_t}{\epsilon_t+\epsilon'_t}$}\\ x_t - \epsilon'_t & \textrm{with probability $\frac{\epsilon_t}{\epsilon_t+\epsilon'_t}$} \end{cases} \end{equation} Note that this means $\mathbb{E}\left[x_{t+1} \bigm| x_t\right]=x_t$. The values for $\epsilon_t,\epsilon'_t$ are chosen such that $0\leq x_t\leq 1$ for all $t$. There are no other restrictions on $\epsilon_t,\epsilon'_t$, e.g. they can be dependent, etc. We stop when $x_t\in\{0,1\}$ (and say, it is guaranteed that we stop in at most $T$ steps).

I am looking for an upper bound on $\displaystyle\sum_{t=1}^T (x_{t+1}-x_t)^2$ in the form of \begin{align*} \Pr\left[\displaystyle\sum_{t=1}^T (x_{t+1}-x_t)^2 > \alpha\right] \leq \beta. \end{align*}

For instance, I think if $\epsilon_t=\epsilon_t'$ for all $t$, then hitting time of the standard brownian motion can give an upper bound? Thanks for your ideas!

share|cite|improve this question
what is the motivation behind this? – Lost1 Nov 1 '13 at 1:50
@Lost1: Using this, I want to get a stronger version of Azuma's inequality for my application; Briefly, it's related to rounding a fractional matching in a matching polytope, and my rounding process is a martingale. Let me know if you want to know more details! – afshi7n Nov 1 '13 at 2:01
Sorry, the left hand-side was not what I meant. it's corrected now. – afshi7n Nov 1 '13 at 8:43

Your Answer


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

Browse other questions tagged or ask your own question.