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 \ln(1/\delta)}\right] \leq \delta$$


My question is:



> 
> Does the same inequality hold if the constants $c\_k$ are not fixed up front, but are themselves a function of the realizations of the previous terms in the martingale $X\_1,\ldots,X\_{k-1}$?
> 
> 
> 


For concreteness, consider the following coin flipping game. An adversary has $n$ coins, which he flips in sequence (represented by random variables $B\_i$ taking values uniformly in $\{-1,1\}$). After observing the outcomes of $B\_1,\ldots,B\_{i-1}$ (but crucially, not $B\_i$), he chooses a non-negative weight $c\_i$. At the end of the $n$ coin flips, we compute the quantity:
$$X\_n = \sum\_{i=1}^n c\_i\cdot B\_i$$


Can we now say that:
$$\Pr\left[X\_N \geq \sqrt{2\sum\_kc\_k^2 \ln(1/\delta)}\right] \leq \delta$$


noting that here, the values $c\_k$ are now random variables themselves?



Adaptive version of the Azuma–Hoeffding inequality
There is no such inequality even if we further restrict $c\_k$ to be in $\{0,1\}$ and weaken the inequality to include a constant factor. (I think it is natural to add the condition that the $c\_k$ values are uniformly bounded.) Suppose $c\_k \in \{0,1\}$ and without loss of generality no $1$ follows a $0$. The choice of $c\_k$ is equivalent to a stopping rule $\tau \le N$. We bet a constant amount on each toss of a coin and decide to stop after $\tau$ flips: $c\_k = 0$ when $k \gt \tau$, so $c\_k$ only depends on $X\_1,...,X\_{k-1}$.


Choose a constant $s \gt 0$. Can we bound 


$$P\left(X\_N \ge s \sqrt{\sum\_{k=1}^N c\_k^2}\right) = P(X\_\tau \ge s \sqrt{\tau})?$$


The [law of the iterated logarithm](https://en.wikipedia.org/wiki/Law_of_the_iterated_logarithm) implies that for an infinite sequence $\{B\_i\}$, the maximum number of standard deviations of $\sum B\_i$ above the mean is almost surely unbounded, hence as $N\to \infty$ the maximum exceeds $s$ with probability approaching $1$. We can let $\tau$ be the minimum of $N$ and the first time $t$ so that $\sum\_{i=1}^{t} B\_i > s\sqrt{t}$.


If you let the bound depend on $N$, something like 


$$P(\max \frac{X\_t}{\sqrt{t}} \ge s) \le f(s,N),$$


then there are nontrivial bounds possible. 


