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).

  • $\begingroup$ (2) doesn't follow from the preceeding line. For example if all the $X_i$ are constants, so that $f$ is a function of $Y$ only, then the left hand side of the preceeding line is 0 for all $y$ and $t>0$ while the left hand side of (2) is in general not 0 . $\endgroup$ – Gideon Schechtman Nov 29 '10 at 10:45
  • $\begingroup$ Yes, I think you are right. (3) does not hold in general. I am still wondering is there any way to give a concentration estimate for such a function $f(X_1,\cdots,X_n, Y)$? $\endgroup$ – Pan Peng Nov 30 '10 at 2:29

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$).


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


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.