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

For a continuous martingale $X$, we have the Doléans-Dade exponential: $$\epsilon(X)_t=\exp\left(X_t-\frac{1}{2}[X]_t\right)$$

What is the "correct" analogue, if one exists, for some discrete-time martingale $M$? (Unfortunately in discrete time this is no longer a (local) martingale.)

The motivation is as follows. On page 68 of these notes, the author proves the Exponential Martingale Inequality (EMI) (quoted in my words):

Let $X$ be a continuous local martingale with $X_0=0$. Then for all $x>0$,$u>0$,

$$\mathbb{P}\left[\sup_{t\geq 0}~ X_s\geq x, [X]_t\leq u\right]\leq \exp\left(-\frac{x^2}{2u}\right)$$

This reminded me of the Azuma-Hoeffding Inequality, which states:

Let $M_n$ be a martingale with $M_0=0$ and $|M_i-M_{i-1}|\leq c_i$ for all $i$. Then, for $x>0$ $$\mathbb{P}\left[\sup_{k\leq n}~M_k\geq x\right]\leq \exp\left(-\frac{x^2}{2\sum_{k=1}^nc_k^2}\right)$$

Well, we have $[M]_n\leq \sum_{k=1}^nc_k^2$, so the former inequality would imply the second if only it were true for discrete-time (discontinuous) martingales (setting $u=\sum_{k=1}^nc_k^2$).

To prove EMI, we apply the optional stopping theorem to $\epsilon(\theta X)$ at the time when the $X$ first hits $x$. This gives a set of bounds parameterized by $\theta$ for the probability we want to bound, and optimizing over $\theta$ gives the result (see notes).

For an appropriate definition of $\epsilon(M)$, would the same argument would work in discrete time (and give a proof of Azuma-Hoeffding)?


share|cite|improve this question

I don't know if this answers the question but here are my two cents :

If we start from the "SDE" definition of Doléans-Dade exponential for a general semi-martingale $X_t$, then the Doléans-Dade exponential is the process $Z_t$ the solution of the following equation :
$$ \begin{cases} dZ_t&=Z_{t-}dX_t, \\ Z_0 &=1. \end{cases} $$

In discrete time this gives an anology which allows us to define the Doléans-Dade exponential as the only dicrete process s.t. :
$$ \begin{cases} \Delta Z_n&=Z_{n-1}\Delta X_n, \\ Z_0 &=1. \end{cases} $$
where $\Delta Y_n$ means $Y_n-Y_{n-1}$ for any discrete process $(Y_n)_{n\ge 0}$. That can be solved by recurence in the form : $$ Z_n=\prod_{i=0}^{n}(1 +\Delta X_i) $$ with the convention $\Delta X_0=0$, so that $Z_0=1$.

Notice that when expressing the solution for time continuous pure jumps semi-martingale you get almost the same answer ( check Jacod, Shiryaev "Limit Theorem for Stochastic Processes" at the end of Chapter 1).

(note that this exponential can take négative values !!!)

Don't know if this helps

Best regards

share|cite|improve this answer

I found a reference to a discrete time result similar the EMI in Exercise 3.11 of the excellent lecture notes Ramon van Handel, Probability in High Dimension (Princeton University, 2014)

The statement of the result is: Let $(M_n)$ be an $(\mathcal F_n)$-martingale, such that for all $n \geq 1$ there exist $\mathcal F_{n-1}$-measurable random variables $A_n, B_n$ such that $A_n \leq M_n - M_{n-1} \leq B_n$, almost surely. Then \begin{equation} \mathbb P\left[ M_n \geq t \ \mbox{and} \ \sum_{k=1}^n (B_k - A_k)^2 \leq c^2 \right] \leq e^{-2t^2/c^2}. \end{equation}

The exercise gives the hint to consider $\lambda M_n - \frac{\lambda^2}{8} \sum_{k=1}^n (B_k - A_k)^2$.

Indeed, we have \begin{align*} \mathbb P \left[ M_n \geq t \ \mbox{and} \ \sum_{k=1}^n (B_k - A_k)^2 \leq c^2 \right] & \leq \mathbb P \left[ \lambda M_n - \frac{\lambda^2}{8} \sum_{k=1}^n (B_k-A_k)^2 \geq \lambda t - \frac{\lambda^2 c^2}{8}\right] \\ & \leq \exp \left( -\lambda t+ \frac{\lambda^2 c^2}{8}\right) \mathbb E\left[ \exp\left( \lambda M_n - \frac{\lambda^2}{8} \sum_{k=1}^n (B_k-A_k)^2 \right) \right]. \end{align*} The Hoeffding lemma states that for $a \leq X \leq b$ a.s., $\mathbb E \left[ \exp( \lambda(X - \mathbb E X ) ) \right] \leq e^{\lambda^2(b-a)^2/8}$. Therefore \begin{align*} \mathbb E \left[ \exp\left( \lambda M_n - \frac{\lambda^2}{8} \sum_{k=1}^n (B_k-A_k)^2 \right)\mid \mathcal F_{n-1} \right] \leq \exp \left( \lambda M_{n-1} - \frac{\lambda^2}{8} \sum_{k=1}^{n-1} (B_k-A_k)^2 \right) \end{align*} and iterating gives that the expectation above is $\leq 1$. Optimizing over $\lambda$ gives the result.

share|cite|improve this answer
See also Dzhaparidze, van Zanten - On Bernstein-type inequalities for martingales, 2001. – Joris Bierkens Nov 14 '14 at 17:39

Suppose we have an $L^1$ discrete time stochastic process $\{X_n\}$, i.e. $E|X_n|<\infty$ for all $n\in\mathbb{N}$. Then since the process is $L^1$ the RV $V_n=\sum_{i=1}^{n}\ln E_{i-1}\left[\exp(X_n-X_{n-1})\right]$ is well-defined. Thus we are generally able to form the exponential martingale $N_n=\exp[X_n-V_n]$.

As an aside, I've found the discrete time exponential martingale to be really useful when dealing with computations for the random walk. It works nicely for the random walk for essentially the same reasons the continuous time analogue works for Brownian motion.

share|cite|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.