Appendix: Learning discrete distributions: user vs item-level privacy A Proof of Lemma 1 Note that ˆp i = (N i + Z