All Questions
16 questions
12
votes
2
answers
2k
views
Can we do better than Azuma-Hoeffding when the variance is small?
The Azuma-Hoeffding Inequality says that if $X_1,X_2, \ldots$ is a martingale and the differences are bounded by constants, $\|X_i - X_{i-1}\| \le 1$ say, then we should not expect the difference $\|...
- 1,955
10
votes
3
answers
4k
views
Extension of the Azuma-Hoeffding inequality (when the differences are bounded with large probability)
Let $(X_i)$ be a super-martingale and suppose their differences are bounded ''with high probability'', that is
$$\mathbb{P}(\exists\,i=1,\dots,n\text{ s.t. }|X_i-X_{i-1}|>c_i) \,\leq\, \epsilon$$
...
- 223
9
votes
2
answers
1k
views
Adaptive version of the Azuma–Hoeffding inequality
The Azuma inequality states that if we have a martingale $X_1,\ldots,X_N$ that satisfies a bounded difference condition:
$$|X_k - X_{k-1}| \leq c_k$$
Then:
$$\Pr\left[X_N - X_0 \geq \sqrt{2\sum_kc_k^2 ...
- 794
8
votes
1
answer
533
views
Concentration bounds for martingales with adaptive Gaussian steps
Consider the following martingale: $X_1 \sim \mathcal{N}(0, 1)$, and for any $n > 1$, $X_n \sim \mathcal{N}(X_{n-1}, X_{n-1}^2)$ (notice, this is a conditional distribution given $X_{n-1}$).
I am ...
- 83
7
votes
2
answers
594
views
Large deviation/concentration inequality for submartingale
Let $S_t = M_t + D_t$ be the sum of a martingale $\left(M_t\right)_{t=1,2,\ldots}$ and a predictable process $(D_t)_{t=1,2,\ldots}$ such that the variance of the increments of $M$ is uniformly bounded ...
- 355
7
votes
1
answer
975
views
Prove an anti-concentration inequality for a martingale
My problem can be described easily:
I have a sequence $(X_l)_{l \in \mathbb{N}}$ of r.v. adapted to some filtration $(\mathcal{F}_l)_{l \in \mathbb{N}}$, such that
$\left|X_{l+1}-X_l\right|\le R$ a. ...
- 73
7
votes
1
answer
466
views
Martingale version of Bernstein-type inequality for (slightly) heavy-tailed distributions?
It is known that for sub-exponentially distributed martingale difference sequence, the following Bernstein-type inequality holds:
$$
ℙ\left(\left|
\sum_{i=1}^N a_i X_i
\right| \ge t \right)
\le
2\...
- 719
7
votes
1
answer
409
views
Do i.i.d. sums concentrate any faster than martingales?
Suppose $X_1,X_2, \ldots, X_N \in \mathbb R^d$ are random variables with each $\|X_n\|_2 \le 1/2$ (this choice of the constant simplifies later formulae).
The simplest concentration inequality I know ...
- 1,955
5
votes
1
answer
165
views
Is there an i.i.d sequence in the unit cube $[-1,1]^d$ with $\mathbb E \left[ \Big \| \sum_{i=1}^N X_N \Big \|_\infty\right] = \sqrt {dN}$?
There are loads of concentration results for sums of scalar-valued independent sums $X_1,X_2,\ldots, X_N$ with $\mathbb E[X_n]=0$. For example Hoeffding's Inequality says if all $|X_1|\le 1$ then $\...
- 1,955
5
votes
0
answers
543
views
Vector martingale concentration
Let $\varepsilon_1, \dots, \varepsilon_N$ be a martingale difference sequence in $R^d$ with $\|\varepsilon_n\| \le B_n, a.s.$ for each $n=1,\dots,N$. Do we have some Azuma-type concentration ...
- 719
4
votes
1
answer
1k
views
Does variants of Bernstein and Freedman concentration inequalities exist with NO uniform bound on the range of RV or martingale differences
A classic formulation of the Bernstein inequality (from Wikipedia) is as follow:
Let $X_1, \ldots, X_n$ be independent zero-mean random variables. Suppose that $|X_i|\leq M$ almost surely, for all $i$...
- 53
4
votes
0
answers
143
views
For a martingale $f_0,f_1,\ldots $ how can we bound $P(\frac{1}{n} \|f_n\| \le 1$ for all $ n \ge N)$?
Suppose $f_0,f_1, \ldots$ is a martingale (or i.i.d sequence) in $\mathbb R^d$ with $f_0=0$ and all $\|f_n - f_{n-1}\| \le L$ say. There are many concentration results for the initial segment of the ...
- 1,955
3
votes
2
answers
636
views
Exponential inequality for the sum of martingale differences $X_1, \dots, X_n$ when $\sum_{i=1}^{n} \operatorname{Var}(X_i) \leq B^2$
Let $X_1, X_2, \dots, X_n$ be a martingale difference sequence such that
$$
X_i \leq y \quad \text{and} \quad \sum_{i=1}^{n} \operatorname{Var}(X_i) \leq B^2.
$$
Question 1: Does the following hold?
$$...
- 33
3
votes
2
answers
319
views
Concentration inequality of joint event over time of a submartingale
Consider a discrete time submartingale $X_n$ with bounded difference $|X_n-X_{n-1}|\leq c$. With Azuma inequality we have the concentration of a single time event as
$$
P(X_t-X_0 \leq -t) \leq exp\...
- 185
2
votes
1
answer
287
views
Bernstein Inequality for continous local martingale
I'm looking for a simple proof of the following fact, which is somehow Bernstein inequality in continuous time.
Let $(M_t)_{t\geq 0}$ be a continuous local martingale. Then :
$$P\left(\sup_{t\in [0,...
- 245
1
vote
1
answer
239
views
Concentration bound for a martingale-like setting (the expected difference decreases as the sequence increases)
I went through several martingales concentration bounds, but none of them fit the settings I am interested in, which is the following. Suppose I have a sequence of nonnegative random variables $0=Y_{0}...
- 225