Problem 11.12 Easy Free 1 variation

Simulating a One-Third Event

You want to simulate an event of probability $1/3$ using only fair coin flips, via the following scheme: flip a fair coin twice. If the result is HH, declare the event to have occurred. If the result is HT or TH, declare that it did not occur. If the result is TT, repeat the two-flip experiment from scratch (independently of the past). Find the expected total number of coin flips used.

Work it out, then compare with the answer.

SolutionShow the worked solution

Each two-flip round ends the procedure unless it shows TT. That happens with probability $\tfrac14$ , so a round is decisive with probability $p=\tfrac34$ , independently of earlier rounds.

Let $N$ be the total number of flips. Condition on the first round. With probability $\tfrac34$ it is decisive and $N=2$ . With probability $\tfrac14$ it is TT. Then two flips have been spent and the process starts afresh, so the remaining number of flips has the same distribution as $N$ . Hence

\mathbb{E}[N]=\tfrac34\cdot 2+\tfrac14\bigl(2+\mathbb{E}[N]\bigr),

which gives $\tfrac34\,\mathbb{E}[N]=2$ , so $\mathbb{E}[N]=\tfrac83$ .

Alternative. The number of rounds $K$ is $\mathrm{Geom}(\tfrac34)$ on $\{1,2,\dots\}$ . So $\mathbb{E}[K]=\tfrac43$ and $\mathbb{E}[N]=2\,\mathbb{E}[K]=\tfrac83$ .

The scheme is correct: given that a round is decisive, it is HH with probability $\frac{1/4}{3/4}=\frac13$ .

\boxed{\mathbb{E}[N]=\tfrac{8}{3}}

Key idea. With independent rounds, the expected cost is (cost per round) $/$ (success probability per round).

Variations

The same idea with a twist. Each solution gives only the changed step.

Variation 11.12a

You wish to sample from $X \sim \mathrm{Beta}(3,2)$ , with density $f(x) = 12x^2(1-x)$ on $(0,1)$ , by acceptance-rejection. You can generate uniform random points in the rectangle $R_a = [0,1]\times[0,a]$ for a chosen constant $a>0$ , and you accept a point $(X,Y)\in R_a$ as a sample whenever it lies under the curve $f$ , rejecting it otherwise. Choosing $a$ to be the smallest value that still makes this a valid rejection scheme (minimizing the rejection rate), find the expected number of rejected points per accepted point.

Work it out, then compare with the answer.

Solution

The scheme is valid only if the curve lies inside the rectangle, that is $a\ge \max f$ .

The point is uniform on $R_a$ , so it is accepted with probability

\frac{\text{area under } f}{\text{area of } R_a}=\frac{1}{a}.

This is largest when $a$ is as small as possible, so take $a=\max f$ .

To find the maximum, note $f'(x)=24x-36x^2=12x(2-3x)$ , which vanishes on $(0,1)$ only at $x=\tfrac23$ . There

f\!\left(\tfrac23\right)=12\cdot\tfrac49\cdot\tfrac13=\tfrac{16}{9}.

Since $f(0)=f(1)=0$ , this is the maximum, so $a=\tfrac{16}{9}$ .

Each point is then accepted independently with probability $\tfrac{9}{16}$ . The number of points generated per accepted sample is $\mathrm{Geom}(\tfrac{9}{16})$ , with mean $\tfrac{16}{9}$ . The expected number of rejected points is therefore

\tfrac{16}{9}-1=\tfrac79.

\boxed{\tfrac{7}{9}}

Spotted an error? Email us