The extension of Markov inequality for submartingales is the Kolmogorov submartingale inequality. For a non negative submartingale $\lbrace Z_m, m \geq 1 \rbrace$ \begin{align*} Pr\left[\max_{1 \leq i \leq m} Z_i \geq a\right] \leq \frac{E[Z_m]}{a} \end{align*}
The extension of Chebychev inequality for submartingales states that for a submartingale $\lbrace Z_m, m \geq 1 \rbrace$ with finite variance \begin{align*} Pr\left[ \max_{1 \leq i \leq m} Z_i \geq b \right] \leq \frac{E[Z_m^2]}{b^2} \end{align*}
The question is: do Chernoff bound also have a submartingale extension? Or alternatively is there a inequality so that threshold crossing have a exponentially decreasing tail w.r.t. the threshold value? Why or why not?
Just found a tentative answer, so I might answer this question myself. Turns out a similar exponential bound can be proved from the Kolmogorov submartingale inequality in exactly the same way the original Chernoff bound can be proved from Markov inequality. A proof can be found here
https://books.google.com/books?id=Q-8Tp201fGMC&pg=PA82&lpg=PA82&dq=moment+generating+function+of+submartingale&source=bl&ots=rCxJLB3WoK&sig=LmGUytge7k09YbHnZL7kl2XAzE0&hl=en&sa=X&ved=0ahUKEwi7rqL4yIzKAhUJ92MKHZ1dCugQ6AEIPjAI#v=onepage&q=moment%20generating%20function%20of%20submartingale&f=false
This is very surprising, because we get from \begin{align*} Pr[Z_m \geq a] \leq E[e^{sZ_m}]e^{-sa} \end{align*} to \begin{align*} Pr\left[\max_{1 \leq i \leq m} Z_i \geq a\right] \leq E[e^{sZ_m}]e^{-sa} \end{align*} for free.