Problem intuition: This problem is about giving a concentration inequality on the sum of bounded differences $\sum_{t=1}^{T} c_td_t$, where each $d_t$ is a bounded difference and $c_t$ is an indicator random variable. In each "round", an "adversary" first draws $c_t \in \{0,1\}$, and then $d_t$ is drawn. Can we argue that the deviation of $\sum_{t=1}^{T} c_td_t$ scales like $\sqrt{\sum_{t=1}^{T} c_t}$?
Problem: Let $\{\mathcal{F}_t\}_{t=0}^{\infty}$ be an increasing filtration, $\{d_t\}_{t=1}^{\infty}$ an adapted process with $\mathbb{E}[d_t|\mathcal{F}_{t-1}] \leq 0$ and $\{c_t\}_{t=1}^{\infty}$ a predictable process (i.e. $d_t$ is $\mathcal{F}_t$-measurable and $c_t$ is $\mathcal{F}_{t-1}$-measurable). Suppose further that we know $\forall t, |d|_t \leq 1$ and $c_t \in \{0,1\}$. For $k \in \mathbb{R}$, can we give a bound on the following?
$$\mathbb{P}\left[\sum_{t=1}^{T} c_td_t > k \sqrt{\sum_{t=1}^T c_t}\right]$$
What I've tried:
I thought of trying to use Azuma's inequality on the supermartingale $\sum_{t=1}^{T} c_td_t$; I tried to walk through the proof to adapt the inequality to this case, but certain steps fail when the right hand side of the inequality isn't a constant. In particular, in wikipedia's proof (https://en.wikipedia.org/wiki/Azuma%27s_inequality), the step where you repeatedly condition and apply Hoeffding's lemma doesn't seem to work when the bounded differences are the random variables |c_t|.
I thought of trying to define a new supermartingale process $X_1,X_2,\dots$ where $X_i=X_{i-1}+$the $i$th non-zero increment, and then applying Azuma's inequality to this sequence. However I think there is a subtlety in conditioning on the indicator random variables which I am not confident about. If we could show that conditional on $\{c_t\}_{t=1}^{T}$ the process $X_1,X_2,\dots$ is a supermartingale, then I think the result would follow. But I'm not sure if this is true or how to approach proving this.
Thanks for your help!