Prove that, for a random variable Z,                             P{Z>} ≤ Ce−cn2 for all > 0  (C > 1,c> 0) implies that                          EZ ≤ :1 + log C cn . Hint: Without loss of generality...

Prove that, for a random variable Z,

                            P{Z>} ≤ Ce−cn2 for all > 0

 (C > 1,c> 0) implies that

                         EZ ≤ :1 + log C cn .

Hint: Without loss of generality assume Z ≥ 0 (otherwise replace Z by Z · I{Z≥0}). Then