# Concentration inequality for conditional probability?

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.
• 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? – 3x89g2 Dec 8 '17 at 18:24
• 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. – ebabio Dec 8 '17 at 21:26
• 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. – ebabio Dec 8 '17 at 21:29