I am trying to understand a part of the proof of an extension of Azuma's inequality, where there is a small failure probability, as it appears in proposition 34 in "Random matrices: universality of local spectral statistics of non-hermitian matrices" by Terence Tao and Van Vu.

Here's the url for Arxiv: https://arxiv.org/pdf/1206.1893.pdf

To my understanding, the basic idea for the proof is that from the original function $Y$ and a martingale sequence ($E[Y|\xi_1,\dots,\xi_{i}])_{i=1}^n$, a modified function $Y'$ and martingale sequence ($E[Y'|\xi_1,\dots,\xi_{i}])_{i=1}^n$ are constructed, by alternating $Y$ on "bad" sets where martingale difference terms are big.

I am having a hard time understanding why the new martingale sequence based on $Y'$ should have the bounded difference, i.e. $|E[Y'|\xi_1,\dots,\xi_{i}]-E[Y'|\xi_1,\dots,\xi_{i-1}]| \leq \alpha_i$ a.s.

Any input will be very much appreciated. Thanks!


The statement "$Y'$ satisfies the condition of Azuma’s inequality" is incorrect in general if it is supposed to mean, for instance, that $C'_i\le C\alpha_i$ for some real constant $C$ not depending on the distribution of $Y$, where $C'_i=C'_i(\xi)$ is defined similarly to $C_i(\xi)$ in definition (4.1) on page 28 in the linked paper but with $Y'$ in place of $Y$: $$C'_i(\xi):=|E(Y'|\xi_1,\dots,\xi_i)-E(Y'|\xi_1,\dots,\xi_{i-1})|.$$

Indeed, suppose that $n=1$, $\xi_1=Y$, $P(Y=n)=\frac1{n+1}=1-P(Y=-1)$ for natural $n\ge2$, so that $EY=0$. Let $\alpha_1=2$. Then $C_1=|E(Y|\xi_1)-EY|=|Y|$, $B_1=\{C_1\ge2\}=\{Y=n\}$, $Y'=1_{B_1}\,E_{B_1}Y+1_{B_1^c}\,Y=1_{Y=n}\,n-1_{Y=-1}$, $C'_1=|Y'|=1_{Y=n}\,n+1_{Y=-1}$, which is not bounded by any constant not depending on the distribution of $Y$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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