A Proof of Theorem 4.1

We first state the following Lemma which we will use to prove Theorem 4.1. We prove this via induction. It's easy to see that this holds true at round First we state the following fact: 15 Fact B.1 Suppose the update requester is non-adaptive. We will prove another upper bound using the max-information bound. Bin (k,p) as we have shown in the first part of this theorem.