Intereting Posts

Non-Trivial Induction Order
A curve parametrized by arc length
Can the “inducing” vector norm be deduced or “recovered” from an induced norm?
Is every Lebesgue measurable function on $\mathbb{R}$ the pointwise limit of continuous functions?
Question(s) about uniform spaces.
Writing a function $f$ when $x$ and $f(x)$ are known
Extended ideals and algebraic sets
“Counterexample” for a weaker version of Riemann–Lebesgue lemma
$J(\mathcal{O})\cong\bigoplus_{\mathfrak{p}} P(\mathcal{O}_\mathfrak{p})$ for one-dimensional Noetherian domains (from Neukirch)
Surprise exam paradox?
Why don't we have an isomorphism between $R$ and $ R]$?
What is the surface by identifying antipodal points of a 2-torus embedded in $\mathbb{R}^3$?
Conformal parametrization of an ellipse
Reference book on measure theory
Is there a name for a topological space $X$ in which very closed set is contained in a countable union of compact sets?

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.

- Expected Number of Coin Tosses to Get Five Consecutive Heads
- Is there an introduction to probability and statistics that balances frequentist and bayesian views?
- Book suggestion for probability theory
- Why is a random variable called so despite being a function?
- Is this condition enough to determine a random variable?
- Expected value of two successive heads or tails (stuck on computation)

- Let $Z$ be standard normal can we find a pdf of $(Z_1,Z_2)$ where $Z_1=Z \cdot 1_{S},Z_2=Z \cdot 1_{S^c}$
- Boy Born on a Tuesday - is it just a language trick?
- Probabilistic approach to prove a graph theory theorem
- How to comprehend $E(X) = \int_0^\infty {P(X > x)dx} $ and $E(X) = \sum\limits_{n = 1}^\infty {P\{ X \ge n\} }$ for positive variable $X$?
- Given two basis sets for a finite Hilbert space, does an unbiased vector exist?
- Solving a simple recurrence relation
- Negative binomial distribution - sum of two random variables
- Probability that $ax^2+bx+c$ has no real roots after rolling 3 dice.
- Expected number of steps till a random walk hits a or -b.
- Probability that a stick randomly broken in two places can form a triangle

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.

- Solving Triangles (finding missing sides/angles given 3 sides/angles)
- All matrices which commute with all $2\times 2$ matrices
- Prove: If $N\lhd G$ and $N$ and $\frac{G}{N'}$ are nilpotent, then $G$ is nilpotent.
- Exact Differential Equations
- On Dirichlet series and critical strips
- The kernel of a continuous linear operator is a closed subspace?
- Proof that rational sequence converges to irrational number
- Are all the finite dimensional vector spaces with a metric isometric to $\mathbb R^n$
- Probability of picked cards to be smaller than the largest picked card
- Show that if f is analytic in $|z|\leq 1$, there must be some positive integer n such that $f(\frac{1}{n})\neq \frac{1}{n+1}$
- Given $P(B\mid A)=1-\varepsilon$ for some $0<\varepsilon<1$ and $P(C\mid B)=1$, prove that $P(C\mid A)≥1-\varepsilon$
- Can a basis for a vector space be made up of matrices instead of vectors?
- How many ways can $r$ nonconsecutive integers be chosen from the first $n$ integers?
- Problem with drawing ellipse with code.
- Not understanding Simple Modulus Congruency