Thread by @ccanonne_

📊 It's Thursday for many, time for this week's quiz! As alluded earlier, we're going to flip coins. Like, a lot.

Today: you have a biased coin which lands heads with some probability p∊(0,1), and you can toss it as many times as you want. You don't know p, though...

1/10

... which is a real shame, since you want to simulate *another* biased coin which lands heads w/ proba exactly f(p), where f: (0,1)→(0,1) is fixed.
(Also, you'd like to do this efficiently, thank you very much.)

Let's start with a simple function: f(p)=1/2.

Q1: Can you?

2/10

OK, so that was the warmup. Let's formalize a bit more what "efficiently" means here. For us, it will mean (1) with a number of coins finite almost surely (no infinite sequence of tosses), and (2) with a finite automaton.

Ha.

A finite automaton.

3/10

No need to worry: this just means a set of rules which says that at each step, you are in one of finitely many "states" and, based on this and the new coin flip you observe, you switch to another of those states (until you reach an "end state").

Q2: What about f(p)=1/7?

4/10

Constants are fun, but... I'm sure there are other functions. I think. Here's another one.

Remember: you don't know p, but this should work for all p!

Q3: What about f(p) = p²(1-p+p²)⁻¹

5/10

Rational functions, am I right. Rationals are easy! We, let's try with a non-rational one...

Q4: What about f(p) = √p?

6/10

Almost there. Maybe square roots were a bit ambitious... after all, your hands are tied: you have to used a simple type of algorithms *and* I require you to simulate sqrt(p)-biased coins?

7/10

Let's go back to a simpler type a function. So, can you come up with a simple procedure (finite automaton, as before) to simulate an f(p)-biased coin given a p-biased...

Q5: for f(p) = 2p?

8/10

To conclude... well, again, you had you hands tieds in the back. Finite automata are not the most powerful objects! It's reasonable to ask what happens if you are allowed fancier procedures.

Q6: Would any of the results change if you were allowed *any* type of computation?

9/10

That's all for today's quiz! Answers and discussion tomorrow (Friday), as usual. In the meantime, feel free to comment below! ↴

[Note: I haven't even mentioned how many coin flips are required, i.e., how "coin-efficient" those computationally efficient processes are...]

10/10