[20] For a binary string x of length n, let f(x) be the number of ones in x. Show that (x) = log(2n1/2|f(x) 1

[20] For a binary string x of length n, let f(x) be the number of ones in x. Show that δ(x) = log(2n−1/2|f(x) − 1 2n|) is a P-test with P the uniform measure.

Comments. Use Markov’s inequality to derive that for each positive λ, the probability of 2n−1/2|f(x) − 1 2n| > λ is at most 1/λ. Source: [T.M.

Cover, P. G´acs, and R.M. Gray, Ann. Probab., 17(1989), 840–865].