Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
(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 . –  Gideon Schechtman Nov 29 '10 at 10:45
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)$? –  Pan Peng Nov 30 '10 at 2:29
add comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.