# Is there a discrete-time analogue of Doléans-Dade exponential?

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)?

Thanks.

-

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

-

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 $$\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}.$$

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.

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

-