I am trying to solve the following exercise (exercise 8.1 from Bucheron, Lugosi, Massart):

Use Marton's transportation inequality to show that if $P$ is a product measure on $\mathcal{X}^n$, then for any pair of measurable sets, $A, B \subset \mathcal{X}^n$, $$ d_H(A, B) \leq \sqrt{\frac{n}{2} \log(1/P(A))} + \sqrt{\frac{n}{2} \log(1/P(A))}, $$ where $d_H(A, B) = \min_{x \in A, y \in B} \sum_{i=1}^n \mathbf{1}_{\{x_i \neq y_i\}}$.

I could really use a hint!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.