Concentration bound using Azuma's inequality and Law of total probability

Question

Given a function $f(X_1,\cdots,X_n,Y)$ on random variables $\{X_i\}$ and $Y$, which is continuous , I want to show that $f$ concentrates around its expectation $\operatorname*{E}[f]$, i.e., a formula like this: $\Pr[|f(X_1,\cdots,X_n, Y)-\operatorname*{E}[f(X_1,\cdots,X_n, Y)]|\geq t]\leq \exp(-\frac{t^2}{2c^2})$, where $c^2$ is the Lipschitz-type bound on $f$.

The case considered here is different from the traditional one which does not have the additional continous random variable $Y$. However, we can still use the traditional way to show the concentration. By the Law of total probability, it is equal to bound $\operatorname*{E}_Y[\Pr[|f(X_1,\cdots,X_n, y)-\operatorname*{E}[f(X_1,\cdots,X_n, y)]|\geq t|Y=y]] \qquad (1)$.

Given $y$ , if we have that $|\operatorname*{E}[f|X_1,\cdots,X_{i-1},X_i=x_i,y]-|\operatorname*{E}[f|X_1,\cdots,X_{i-1},X_i=x'_i, y]\leq c_i(y),$ for all $i$ with $1\leq i\leq n$ and any $x_i,x'_i$.

then by the stardard use of Azuma's inequality, $\Pr[|f(X_1,\cdots,X_n, y)-\operatorname*{E}[f(X_1,\cdots,X_n, y)]|\geq t|Y=y]\leq \exp(-\frac{t^2}{2\sum_{i=1}^n c_i^2(y)})$.

Thus, from (1), $\Pr[|f(X_1,\cdots,X_n, Y)-\operatorname*{E}[f(X_1,\cdots,X_n, Y)]|\geq t]\leq \operatorname*{E}[\exp(-\frac{t^2}{2\sum_{i=1}^n c_i^2(Y)})] \qquad (2)$

My question is that can the above inequality be improved as: $\Pr[|f(X_1,\cdots,X_n, Y)-\operatorname*{E}[f(X_1,\cdots,X_n, Y)]|\geq t]\leq \exp(-\frac{t^2}{2\sum_{i=1}^n \operatorname*{E}[c_i(Y)]^2}) \qquad (3)$.

P.S. I think that the Jassen's inequality (i.e., $\operatorname*E[g(Z)]\geq g(\operatorname*E[Z])$ for convex function $g$) may be useful here, but I donot see the convexity of the right hand of inequality (2).

Answer 1

See my comment above for some problem in your argument but anyhow (3) is wrong. If the $X_i$-s are constants then the right hand side of (3) is 0, while the left hand side is not in general. If you don't like to use constant r.v.: if each of the $X_i$ takes values in a small interval, the right hand side is arbitrarily close to zero while the left hand side not, in general (say, for the function $f(x_1,...,x_n,y)=y$ and any reasonable $Y$).

Answer 2

The concentration of $f$ follows directly from McDiarmid's inequality and the fact that $f$ is Lipschitz. See e.g. http://cs.nyu.edu/~rostami/ml/2007/ashish-mcdiarmid.pdf