Fano's inequality

Given two random variables $X$ and $Y$ which are correlated, Fano's inequality quantifies the probability of error when using $Y$ to estimate $X$, by relating it to the conditional entropy $H(X|Y)$. Call the probability of error $P_e$, then

$P_e \geq \frac{H(X|Y)-1}{\log{|\chi|}}$

where $\chi$ is the set over which $X$ takes values.

One can also prove using Jensen's inequality that for two i.i.d. random variables $X$ and $X'$:

$P(X=X')\geq2^{-H(X)}$

with equality iff X is uniformly distributed.