Thread by @ccanonne_

📊 It's Thursday: time for our wÆkly quiz! I'll build a little bit on last week's statistics/algorithms thread (see below for a recap), and ask you two 2️⃣ questions.

General topic: testing distributions, "leaky" measurements, and adaptivity. 🔍

1/6

https://twitter.com/ccanonne_/status/1285114718928039936

Suppose you have the following type of measurements: at each time step, you get to specify a subset S⊆[k], your "question"; and *try* to observe a fresh sample x from the unknown distribution p (over [k]). With probability η, you get to see x: it's leaked to you 🎁...

2/6

... but with probability 1-η, you only get to know if x is in S. (Think of it as yes/no ❓, but w/ an η chance to get full info 🎁.)

We'll fix η=1/√k: you don't win 🎁. often. Your goal: test if p is uniform, or at large statistical distance (TV) from uniform, say 1/100.

3/6

So, OK, you can do that for n steps. How many steps do you need, as a function of k? (Recall: we fixed η=1/√k)

Q1: Suppose you must be *non-adaptive*: that is, you have to specify all the "questions" (subsets) S₁,..., Sₙ ⊆[k] ahead of time. How many steps do you need?

4/6

Cool. But we tied your hands behind your back: you had to choose all your questions S₁,..., Sₙ in advance!

Q2: What if we allow you to choose them *adaptively*, i.e., at step t you can choose Sₜ as a function of the answers to the previous t-1 questions? How many steps?

5/6

That's all for today. As usual, answers and discussion tomorrow!

In the meantime, feel free to comment below ↴. If you can't wait: the answers *may* be hidden in this recent paper 📄arxiv.org/abs/2007.10976, and one *may* be related to one of the algos from last week! :)

6/end