Jointly distributed random variables (a) and (b) are distributed on the n-element set.
Let $\varepsilon = Prob(a \ne b)$
It is needed to prove that $H(a|b) \le 1 + \varepsilon log(n-1)$.
I tried to prove it by representing $H(a|b)$ as $H(a|b) = - \sum_{i=1}^n \sum_{j=1}^n p(a_i,b_j) log(p(b_j|a_i)$ and exrtracting a part where $b_j = a_i$, but without any succcess. Could you help me please. Thank you in advance.
This is basically Fano's inequality.
Sketch: Let $x$ be a random variable such that $x=1$ iff $a=b$, $x=0$ otherwise. Then use the chain rule (conditioned on $b$):
$$H(a,x|b)=H(a|x,b) + H(x|b) = H(x|a,b)+H(a|b)$$
Then note that $H(x|a,b)=0$, and $H(x|b)\le H(x)\le 1$. Furthermore, $H(a|x,b)=P(x=0) H(a|x=0,b) + P(x=1)H(a|x=1,b)$ with $H(a|x=1,b)=0$ and $H(a|x=0,b)\le \log(n-1)$