Homework #5 graded

Homework 5 is graded. The average was 90%, with two people getting 39/40.

Most problems were done pretty well; interestingly, only one person attempted #7, even though it has the shortest solution after #3. A number of people did #2 but no one really got part (b) exactly correctly. The issue there is that you have a real-valued (not integer-valued) random variable and you know that it has exponentially small tails; you want to show that the contribution to its $L_1$-norm from large numbers is exponentially small. There is a battle here, between, the contribution of $\mid u\mid$ and the probability $O\left(e^{-u^2/2}\right)$, which of course the exponentially small quantity is going to win; still, one has to integrate, as shown in the solutions.

Also, nobody got #6(c) quite correct. The Tribes function is not exactly balanced; its empty Fourier coefficient is just known to be $\pm O(\log n/n)$. Thus $\mathbb{N}{}_{1/2-\gamma }\left(T\right)$ will always be at most $1/2-\Omega ({\log }^{2}n/n^2)$, which is why the condition $\gamma \ge 1/n$ is necessary.


I'm also pleased to report that the overall homework average was 83%. Good job, y'all.