Cover’s test for the irrationality of a coin

Someone hands you a coin which has a probability $p$ of coming up heads. You can flip the coin as many times as you like (or more precisely, you can flip the coin an infinite number of times). Let $S = \{r_i : i = 1, 2, \ldots\}$ be the set of rational numbers in $[0,1]$ . After each flip, you have to guess one of the following hypotheses: that $p = r_i$ for a particular $i$ , or $p$ is irrational. Furthermore, you can only make a finite number of errors for any $p \in [0,1] - N_0$ , where $N_0$ is a set of irrationals of Lebesgue measure 0. Can you do it? If so, how?

This is the topic addressed by a pair of papers that Avrim Blum mentioned in Yoav Freund‘s remembrances of Tom Cover:

COVER, THOMAS M (1973). On determining the irrationality of the mean of a random variable. Ann. Math. Statist. 1862-871.
COVER & HIRSCHLER (1975). A finite memory test of the irrationality of the parameter of a coin. Annals of Statistics, 939-946

I’ll talk about the first paper in this post.

The algorithm is not too complicated — you basically go in stages. For each time $j = 1, 2, \ldots$ you have a function $n(j)$ . Think of $n(j)$ as piecewise constant. There are two sequences: a threshold $k_{n(j)}$ , and an interval width $\delta_{n(j)}$ .

Take the sample mean $\hat{x}_{n(j)}$ and look at a interval of width $2 \delta_{n(j)}$ centered on it. Note that this makes the same decision for each $j$ until $n(j)$ changes.
Given an enumeration of the set $S$ , find the smallest $i$ such that $r_i \in [\hat{x} - \delta_{n(j)}, \hat{x} + \delta_{n(j)}]$ .
I there is an $i < k_{n(j)}$ such that $r_i \in [\hat{x} - \delta_{n(j)}, \hat{x} + \delta_{n(j)}]$ then declare $p = r_i$ , otherwise declare $p \notin S$

The last thing to do is pick all of these scalings. This is done in the paper (I won’t put it here), but the key thing to use is the law of the iterated logarithm (LIL), which I never really had a proper appreciation for prior to this. For $\epsilon > 0$ ,

$| \hat{x}_n - p | \le (1 + \epsilon) (2 p (1 - p) \sqrt{ \frac{\log \log n}{n} })$

for all but finitely many values of $n$ . This gets used to set the interval width $\delta_{n(j)}$ .

The cool thing to me about this paper is that it’s an example of “letting the hypothesis class grow with the data.” We’re trying to guess if the coin parameter $p$ is rational and if so, which rational. But we can only apprehend a set of hypotheses commensurate with the data we have, so the threshold $k_{n(j)}$ limits the “complexity” of the hypotheses we are willing to consider at time $j$ . The LIL sets the threshold for us so that we don’t make too many errors.

There are lots of little extensions and discussions about the rationality of physical constants, testing for rationality by revealing digits one by one, and other fun ideas. It’s worth a skim for some of the readers of this blog, I’m sure. A miscellaneous last point : Blackwell suggested a Bayesian method for doing this (mentioned in the paper) using martingale arguments.

6 thoughts on “Cover’s test for the irrationality of a coin”

I think the null hypothesis is just p \in [0, 1] – N_0, and N_0 is a set of irrationals, not rationals?

Anand Sarwate says:

on April 18, 2012 at 3:24 pm

Oops poor phrasing, will rephrase…

Reply
Anand Sarwate says:

on April 18, 2012 at 3:26 pm

Rather : yes, a typo, plus a misstatement of the problem. Fixed now!

Reply
rif says:

on April 18, 2012 at 5:35 pm

No wait, I’m confused.

Reply
- Anand Sarwate says:
  
  on April 18, 2012 at 7:42 pm
  
  So the setup is as follows — there are countably many hypotheses, one for each rational, and the null hypothesis, which is that p is irrational. You get to come up with a sequential testing procedure.
  
  Now I will test your procedure with each p \in [0,1]. It has to make a finite number of errors for all values of p in a set [0,1] – N_0, where N_0 has Lebesgue measure 0. So, for example, it can fail to have a finite number of errors for all p in the Cantor set minus the rationals.

This is a really cool problem. Tom Cover used to really like these ‘daylight robbery’ kind of puzzles, where the first reaction to hearing the problem statement is to declare that it is impossible. I will read the paper.

	Zonghong Liu on A story about Canvas
	anonymousskimmer on “The needs of the many,…
	Chanterelle Recipes… on Broiled shrimp with chanterell…
	kvarsh on ICML 2019 encouraged code subm…
	Pulkit Grover on gender inclusivity in communic…

S	M	T	W	T	F	S
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

An Ergodic Walk

a process whose average over time converges to the true average

Cover’s test for the irrationality of a coin

6 thoughts on “Cover’s test for the irrationality of a coin”

Leave a Reply Cancel reply

Share this:

Like this:

Related

6 thoughts on “Cover’s test for the irrationality of a coin”

Leave a Reply Cancel reply