Intereting Posts

Are there Hausdorff spaces which are not locally compact and in which all infinite compact sets have nonempty interior?
How to compute $\int \sqrt{\frac{x^2-3}{x^{11}}}dx$
Prove that Q has an automorphism of order 3.
What does the factorial of a negative number signify?
At large times, $\sin(\omega t)$ tends to zero?
How to either prove or disprove if it is possible to arrange a series of numbers such the sum of any two adjacent number adds up to a prime number
How to find $\mathbb{E}$?
Example of a commutative ring with identity with two ideals whose product is not equal to their intersection
Prove that $\sum\limits_{n=1}^{\infty}\left (1-\dfrac{a_{n}}{a_{n+1}}\right)$ converges.
Factoring morphisms in abelian categories
Does $\sum \limits_{n=1}^\infty\frac{\sin n}{n}(1+\frac{1}{2}+\cdots+\frac{1}{n})$ converge (absolutely)?
Bockstein homomorphism and Steenrod square
No closed form for the partial sum of ${n\choose k}$ for $k \le K$?
Bijection between an infinite set and its union of a countably infinite set
Solution of $19 x \equiv 1 \pmod{35}$

We would like to choose between theatre and cinema by tossing a coin. Unfortunately the only available coin we have has probapility of heads $p\ \left(\dfrac{1}{2}<p<1\right)$. How could we use that coin to take a good decision so that the two options have equal possibilities?

My solution: we will flip the coin twice, if it comes up heads first and tails second, then we will go to the theatre. If it comes up tails first and heads second, then we will go to the cinema. If the two flips are the same, we flip twice again, and repeat the process until we have a unbiased toss. Is it correct?

*Note added by joriki*: As discussed in the comments, I’m reopening the question because of the aspect that the probability $p$ of heads is known and may be used to optimise the algorithm; this aspect was not present in the question Puzzle about technique of fair using of unfair coin as a duplicate of which this question had been closed.

- The Last Man Standing
- Kelly criterion with more than two outcomes
- Continuously sampled event: Estimating the value of a future data point, based on past measurements and their tendency
- Expected Ratio of Coin Flips
- “off by 1” lottery probability
- How to compute the sum of random variables of geometric distribution

- Toss a coin 10 times, run of 4 head occurs
- Count the number of possible solutions
- Is this urn puzzle solvable?
- Probability Density Function Validity
- What is the average length of 2 points on a circle, with generalizations
- Conditional probabilities from a joint density function
- How to explain why the probability of a continuous random variable at a specific value is 0?
- Best strategy to pick a lock which opens if at least two of its three decimal digit wheels are dialed correctly?
- Joint distribution of dependent Bernoulli Random variables
- Monty Hall Problem with Five Doors

As already discussed in comments, your algorithm is correct and doesn’t require knowledge of $p$. There is an improved algorithm, mentioned in a comment by user21820, that also doesn’t require knowledge of $p$ and is optimal in the sense that it converts a stream of biased flips into a stream of unbiased flips at the maximal rate determined by the entropy of the biased distribution.

However, as you only want to go to the theatre or the cinema once (by the way: why not go to a movie theatre?), you’re probably not interested in the long-term conversion rate of an infinite stream but in the expected number of flips required to make this one-off decision.

In the algorithm you propose, you essentially perform trials consisting of two flips each, with a success probability of $2p(1-p)$. Thus the expected number of flips is

$$

2\cdot\frac1{2p(1-p)}=\frac1{p(1-p)}\;,

$$

which is anywhere from $4$ for $p=\frac12$ to arbitrarily large numbers for $p\to1$.

The notes on the improved algorithm linked to above derive the expected time it requires to produce a bit. (The analysis is carried out for an algorithm that’s not quite as sophisticated as the one that achieves the optimal flip rate, but the two algorithms coincide until the first unbiased flip is produced.) The result is

$$

2\prod_{k=1}^\infty\left(1+p^{2^k}+(1-p)^{2^k}\right)\;.

$$

This is a bit of an improvement, with values ranging from about $3.4$ for $p=\frac12$ to arbitrarily large numbers for $p\to1$.

But there’s actually a simpler approach that does considerably better, in the spirit of arithmetic coding. Let’s generalise the problem to using the biased coin with heads probability $p$ to simulate another possibly biased coin with heads probability $q$. We can then apply this with $q=\frac12$ to simulate a fair coin.

The basic idea is that for all $p$ and $q$ there is always one result $A$ of the real coin that is at most as probable as one result $B$ of the simulated coin, so we can stop with result $B$ when $A$ occurs and continue with a suitable new value of $q$ if it doesn’t. The result can be defined recursively (with $0$ representing tails, $1$ representing heads, $X(q)$ a simulated result with heads probability $q$ and $Y(p)$ an actual result with heads probability $p$:

$$

X(q)=\begin{cases}

0&q\lt p\land Y(p)=0\;,\\

1&q\ge p\land Y(p)=1\;,\\

X\left(\frac qp\right)&q\lt p\land Y(p)=1\;,\\

1-X\left(\frac{1-q}{1-p}\right)&q\ge p\land Y(p)=0\;.

\end{cases}

$$

for $q\ge\frac12$, and $X(q)=1-X(1-q)$ otherwise. (This is to be read more like pseudocode for a recursive program than a mathematical definition, as the variables $X$ and $Y$ stand for different quantities in each iteration.)

I haven’t been able to figure out the expected number of throws to produce the first unbiased flip with this algorithm, but here are the results of simulations (in red), graphed together with your simple algorithm (in purple), the more elaborate algorithm linked to above (in green) and the lower bound $-\log2/(p\log p+(1-p)\log(1-p))$ from entropy (in blue):

The improvement is substantial; you need roughly half as many throws on average. Here’s the code for the simulations.

- Definition of e
- Closed maps in terms of “thickening fibers”
- An elliptic curve for the multigrade $\sum^8 a_n^k = \sum^8 b_n^k$ for $k=1,2,3,4,5,9$?
- How to solve this equation? $x^2 – y^2 = 5$ & $ xy = 2$. Find $x$ and $y.$
- Properties of automorphism group of $G={Z_5}\times Z_{25}$
- Explicit homeomorphism between open and closed rational intervals?
- Are all algebraic commutative operations always associative?
- Proving that $\lim_{n\rightarrow \infty} \frac{n^k}{2^n}=0$
- Equivalence of tensor reps & tensor products of reps
- Derivation of the Riccati Differential Equation
- Elements of the form $aX^2 + bY^2$ in a finite field.
- Compute $\phi_X(t)=E(e^{it^\top X})$ if $X\stackrel{d}{=}\mu + \xi AU$ with $AA^\top=\Sigma$
- Uniform Convergence of a Nonlinear Sequence of Functions #1
- Is every $\sigma$-algebra generated by a partition?
- Subgroups of $S_{4}$ that contain the kernel of a homomorphism $\varphi:S_{4}\to S_{3}$