How does "concentration inequalities" for conditional probability works? The conditional probability I am considering is

$$\mathbb{P}\left\{ \left| v'(A) - v_n(A)\right| < \frac{\epsilon}{2} \mid Z_1,\cdots,Z_n \right\}$$

where $v(A) = \mathbb{P}\left(Z_1 \in A\right)$ and $v_n'(A) = \frac{1}{n}\sum_{i=1}^n I(Z'_i \in A)$ (so-called empirical measure). In total, we have $2n$ iid random variables: $Z_1,\cdots,Z_n ,Z_1', \cdots,Z_n'$.

The derivation I have claims that "bounded by Chebyshev's inequality", we have

\begin{align*} \mathbb{P}\left\{ \left| v_n'(A) - v(A)\right| < \frac{\epsilon}{2} \mid Z_1,\cdots,Z_n \right\} \ge 1 - \frac{v(A)(1 - v(A))}{n\epsilon^2/4} \end{align*}

What I understand: I recognize that $\mathbb{E}\left[ v'_n(A)\right]=\frac{1}{n}\sum_{i=1}^n\mathbb{E}\left[ I(Z_i' \in A) \right] = \mathbb{P}\left(Z_1\in A\right) = v(A)$. Also, I understand that $\text{Var}\left[ v'_n(A)\right] = v(A)(1-v(A))$

What I don't understand: How Chebyshev's inequality can/should be applied to a conditional probability? First, in the usual setting, the probability we want to bound is really a number, but a conditional probability is a random variable. So what does the upper bound here exactly means? Bounded almost everywhere? I don't quite understand how conditional affects how things work out here...


I think the key is to realize that once a random variable is conditioning another variable it does not behave as random variable anymore, but a non-random function. For example, the following two expressions are equivalent: $$ P(X<x | Z) = P(X<x | Z=z) $$

So the same way $P(X<x)$ is a non random function of $x$, $P(X<x | Z=z)$ is a non random function of $x$ and $z$. From this perspective, applying Chebyshev's inequality or any other expression involving constants should be straightfoward.

| cite | improve this answer | |
  • $\begingroup$ By definition 13.1.4 from A First Look at Rigorous Probability Theory, "P(A\imid X) is a conditional probability of $A$ given $X$ if it is a $\sigma(X)$-measurable random variable." So you are suggesting this random variable is always constant? $\endgroup$ – 3x89g2 Dec 8 '17 at 18:24
  • $\begingroup$ Just to be clear about nomenclature. Non-random does not imply it is constant. In the usual sense of calculus $f(x)$ is not constant but it is non-random because neither $x$ nor $f(·)$ are random, but for a random variable $X$, $f(X)$ will be non-constant AND random because $X$ is random. $\endgroup$ – ebabio Dec 8 '17 at 21:26
  • $\begingroup$ Now, conditioning on a random variable means that you will be assigning $X=x$, i.e, you are assuming that a random-variables becomes non-random and takes a deterministic value $x$ that can be non-constant (as in $f(x)$). Usually, this $P(A | X)$ means $P(A | X=x) $ for all possible $x$ values that $X$ can take. Therefore what $X$ does is define the domain of possible values that the non-random $x$ can take. $\endgroup$ – ebabio Dec 8 '17 at 21:29

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.