4

What numbers in the interval $[0,1]$ can be generated by tossing a fair coin? By generating a number using a coin, we mean finding an event that its probability is the given number.

I think that any number in $[0,1]$ can be generated by tossing a fair coin for an infinite number of times because we can generate the binary expansion. And by generating, I mean finding an event that gives the desired probability.

So, it seems that if tossing a coin for an infinite number is allowed, the problem's done. However, what if we disallowed tossing for infinitely many times? Then I think only those numbers whose denominator are a power of $2$ can be expressed. Others cannot be expressed. But I am not sure. Any help is appreciated.

stressed out
  • 8,130
  • 2
    $P[\mbox{H or HT}] = P[H] = 1/2$. (Since $HT \subseteq H$). – Michael Oct 13 '18 at 07:42
  • @Michael Oops, you're right. And it seems like this argument cannot be saved in any easy way. Thanks for pointing it out. – stressed out Oct 13 '18 at 07:44
  • This is a classic problem and you can surely find the solution online somewhere. Anyway, if you think about infinite coin tosses you generate a random variable $X$ uniform over $[0,1]$, and for a given number $x \in [0,1]$ you can consider things like $P[X\leq x]$. For any $x \in [0,1]$, the event ${X \leq x}$ can evaluated in a number of coin flips that has finite (and surprisingly small) expectation. – Michael Oct 13 '18 at 07:48
  • @Michael Could you please point me to a reference/solution for the problem? I did Google the problem, but I couldn't find it. – stressed out Oct 13 '18 at 07:50
  • I was intentionally trying not to...so you could use the above hints. First, evaluate $P[X\leq x]$. Then, describe how to determine the truth/falsehood of ${X \leq x}$. (Perhaps "Zeroth" is to define how the random variable $X$ is related to the coin tosses.) – Michael Oct 13 '18 at 07:51
  • @Michael Yeah, but before I try to evaluate $P[X \leq x]$, I should figure what $X$ has to be. No? I appreciate that you didn't give out the solution. I'm thinking about something like an accept-reject algorithm but I'm not sure. I should think more about it. But am I at least in the right direction? – stressed out Oct 13 '18 at 07:59
  • If $X$ is uniform over $[0,1]$ then $P[X\leq x]$ is... – Michael Oct 13 '18 at 08:00
  • @Michael Haha (facepalm). $P[X \leq x] = x$, but I'm thinking about how to find the r.v. $X$ itself. That's the problem. No? – stressed out Oct 13 '18 at 08:02
  • For that you can imagine flipping the coin an infinite number of times. Afterward you can work out htat finding the truth/falsehood of ${X \leq x}$ does not require knowledge of all the flips. – Michael Oct 13 '18 at 08:03
  • @Michael So, is it something like this: I have an interval $[0,1]$ and at each step, I divide it into $2^n$ parts. Each time I flip the coin, I end up in one half of the subinterval of length $2^{n-1}$ where my last position was. Therefore, I can randomly reach any number in $[0,1]$ with uniform probability. Is the argument something like this? – stressed out Oct 13 '18 at 08:06
  • Wait, what is $n$? You cannot generate $X$ uniform over $[0,1]$ in a finite number of flips. And an interval of length $2^{n-1}$ sounds like it would be an interval with size larger than 1. So, you need to refine your "Zeroth step." – Michael Oct 13 '18 at 08:23
  • Well, determining the truth or falsehood of ${X \leq x}$ seems trivial. I just consider the binary expansion of $x$ as a sequence $x_n$. The first index that my string $s_n$ obtained by tossing the coin has the property that $s_m > x_m$ is where things go bad. So, define a new random variable by $Y$ which gives this index. The expectation of $Y$ is what you were referring to in your initial post. Right? We have already shown that any number from $[0,1]$ can be generated by tossing a coin. So, we're done now. Is there still anything left to be proven? And could you give the reference now? – stressed out Oct 13 '18 at 08:27
  • @Michael No, I didn't mean that it could be generated in a finite number of steps. $n$ is our $n$-th step. We have a stochastic process $X_n$. The $n$ I wrote refers only to this. I didn't mean that it could be done in a finite number of steps. Please read my previous comment. Does that make sense? Are we done or not yet? xD – stressed out Oct 13 '18 at 08:28
  • @Michael Moreover, $\mathbb{E}(Y) = \sum_{n=1}^\infty \frac{n}{2^n} = 2$. Am I right? – stressed out Oct 13 '18 at 08:45
  • You want the first index for which $X_m \neq x_m$. Yes, the expected number of flips needed is 2. – Michael Oct 13 '18 at 14:01
  • Why $X_m \neq x_m$? Aren't we looking for $X \leq x$? what can go wrong if $X_m \leq x_m$ for some $m$? – stressed out Oct 13 '18 at 22:08
  • The first time you see $X_m \neq x_m$, you can decide the truth/falsehood of ${X<x}$. – Michael Oct 14 '18 at 04:32

2 Answers2

1

Write $0.$ and now start tossing the coin. Write $1$ if it comes up heads and $0$ for tails. You will gradually spell out a binary representation of a number in the range $[0, 1]$. As you say, if you stop after a finite number of throws then it will represent $\frac{m}{2^n}$ but you could get an event of probability $\frac{1}{3}$ by comparing against $0.01010101...$. Stop when you get a value definitely above or below this. If you are incredibly unlucky you might never stop.

badjohn
  • 8,204
0

Yes, you're right. And in the finite case, remember that the probability of an event $A$ is the sum of the probabilities of the individual outcomes $a\in A$. So you can only get numbers of the form $$\sum_{i=1}^k 2^{-n_i}$$ where $n_i$ and $k$ are nonnegative integers. Now can you always solve equations like $$\frac1{2^2}+\frac1{2^8}=\frac{x}{2^{y}}$$ for nonnegative integers $x$, $y$?

Bjørn Kjos-Hanssen
  • 2,915