A lot of the confusion and misunderstandings and paradoxes around the Monty-Hall-Discussion arise from the different interpretations of the game with either a "knowing host" or an "ignorant host". Some people do that math based on an ignorant host, some assume the host knows. But today, I want to propose a method that we can actually use to *test* the host's knowledge.

This is my setup:

You are only ever brought into the TV studio when there has been one door reserved for you (randomly of course) and one door opened and showing a goat. Thats what you see, and you play this setup 100 times. And I believe you can determine whether the host knew where the car was or not.

Here is how: If you play the "stay"-strategy, you would expect to win 33% of the games. but this will only happen if you see all the games. If the host accidentely reveals the car, the game is aborted and you will never see it. In this case (Monty does not know) you will observe that your win-rate is 50%. And then you know that there were games you never saw.

I have written a Javascript simulation for this, and it seems to work. I also asked AI for a comment, and it confirmed my approach. Nevertheless I find it wiered that it works. Or am I missing something?

Suppose I have a standard deck of cards, no cards missing and no abnormal cards added. If I shuffle the deck and draw one card at random, the odds of it being a spade are 1 in 4. That's pretty straightforward.

However, what if I put the card back in the deck, reshuffle, and draw another card? And I repeat this cycle X number of times (that is... X times I shuffle, X times I draw, and X-1 times I put the card back). I want to know what the odds are of me drawing a spade at least once.

And while we're at it, I'd also like to know the equation if there are a different number of suits. What if there's 3 suits and 39 cards? Or what if there's a 5th suit and 65 cards? Let's say that "1/s" represents the odds of me drawing a spade, with S representing the number of suits in the deck. And I draw after shuffling X number of times. What's the equation to determine the likelihood then?

Background

We're given a coin that shows heads with an unknown probability, λ. The goal is to use that coin (and possibly also a fair coin) to build a "new" coin that shows heads with a probability that depends on λ, call it f(λ). This is the Bernoulli factory problem (Keane and O'Brien 1994), and I catalog algorithms to solve it.

Main Question

Prove or disprove: Let f:(D⊆[0,1])→[0,1]. Given a coin that shows heads with probability λ (which can be 0 or 1), it is possible to toss heads with probability f(λ) using the coin and no other sources of randomness (and, thus, f is strongly simulable) if and only if—

• f is constant on its domain, or is continuous and polynomially bounded on its domain (polynomially bounded means, both f and 1−f are bounded below by min(x^n, (1−x)ⁿ⁾ for some integer n [Keane and O'Brien 1994]), and
• f(0) and f(1) are each 0, 1, or undefined, and
• if f(0)=0 or f(1)=0 or both, then there is a polynomial g(x):[0,1]→[0,1] with computable coefficients, such that g(0)=f(0) and g(1)=f(1) whenever 0 or 1, respectively, is in the domain of f, and such that g(x)>f(x) for every x in the domain of f, except at 0 and 1, and
• if f(0)=1 or f(1)=1 or both, then there is a polynomial h(x):[0,1]→[0,1] with computable coefficients, such that h(0)=f(0) and h(1)=f(1) whenever 0 or 1, respectively, is in the domain of f, and such that g(x)<f(x) for every x in the domain of f, except at 0 and 1.

It's possible that the conditions given are not necessary, and stronger conditions hold; for example: "0 is not in the domain of f, or f can be extended to a Lipschitz-continuous function on [0,ϵ) for some ϵ>0". A tricky example of such a function is f(x)=(sin⁡(1/x)/4+1/2)⋅(1−(1−x)ⁿ ) for n≥1 (f(0)=0), which is strongly simulable at 0 and is Lipschitz at, say, [0,0.01]. ((1−x)ⁿ is the probability of the biased coin showing zero n times in a row.)

For details, see my progress on this problem.

(In this post, "f(x) is undefined" means that x is not in the domain of f.)

The rest of this page will detail the problem.

Simulable and strongly simulable functions

There are two kinds of factory functions:

• A function f(λ) is simulable if an algorithm exists to toss heads with probability f(λ) given a coin with probability of heads λ (the "biased coin") as well as a fair coin.
• A function f(λ) is strongly simulable if an algorithm exists to toss heads with probability f(λ) given only a coin with probability of heads λ.

Every strongly simulable function is simulable, but not vice versa.

In fact, Keane and O'Brien (1994) showed already that f(λ) is strongly simulable if f is simulable and neither 0 nor 1 is in f's domain (that is, if the biased coin doesn't show heads every time or tails every time). And it's also easy to show that if f is strongly simulable, then f(0) and f(1) must each be 0, 1, or undefined.

However, it's not so trivial to find the exact class of strongly simulable functions when f's domain includes 0, 1, or both.

As one illustration of this, the proof of Keane and O'Brien relies on generating a geometric random variate and using that variate to control which "part" of the target function f(λ) to simulate. This obviously works on all of [0, 1] if the algorithm uses both the biased coin and a separate fair coin. However, if only the biased coin is used in the algorithm, the geometric random variate is generated using fair bits via the von Neumann method, which however will never terminate if λ is either 0 or 1. In addition, a result I found gives sufficient conditions for being strongly simulable when f's domain includes 0, 1, or both. Its proof proceeds by showing, among other things, that the Bernoulli factory for f must flip the input coin and get 0 and 1 before it simulates any fair coin flips via the von Neumann trick.

References

• Keane, M. S., and O'Brien, G. L., "A Bernoulli factory", ACM Transactions on Modeling and Computer Simulation 4(2), 1994. https://doi.org/10.1145/175007.175019