2

Is there some probability distribution that can be implemented/defined/etc. without irrational numbers such that it returns 1 an irrational proportion $P$ of the time and 0 the rest of the time, for any irrational probability $P$? If not, for what irrational $P$ can this be done? I am specifically trying for quadratic irrationals.

When I assume I have some random infinite sequence of bits to use, I want $\Bbb E(X) = \frac 12 \Bbb E(X_0) + \frac 12\Bbb E(X_1)$, where $X_0, X_1$ are results after getting 0 or 1 as the first bit respectively, but this prevents getting irrational from rational it seems, since the two expected values on the right must be irrational, but can't without starting irrationals. This would imply that it needs to be a more complicated process.

I want this to be a distribution that a computer program could in theory run, where irrational numbers cannot occur but I still want an irrational probability.

Edit: In principle I would like to have no approximate arithmetic, since if I could I could just generate a random floating point number between 0 and 1 and check if it's less than the given P (represented inexactly). I am fine with programs that have an indefinitely long running time as long as they are fast in the average case.

Edit: I really want a way to do this for any quadratic irrational, but if it isn't possible I would want to know that it is impossible instead.

Fricative Melon
  • 170
  • Not sure what you mean by "without irrational numbers". Try this: Inscribe a circle in the unit square. Let $X=1$ if a uniformly random point in the square is inside the circle, $0$ otherwise. Is that an example? – lulu Dec 16 '15 at 00:06
  • Note: To implement the "circle process" just note that we are talking about the circle of radius $\frac 12$ which we can think of as the curve $x^2+y^2=\frac 14$. Accordingly, just choose $x,y\in [-\frac 12, \frac 12]$ uniformly and check if $x^2+y^2≤\frac 14$. – lulu Dec 16 '15 at 00:23
  • Are you using approximate arithmetic? Using arbitrary precision, lulu's suggestion works: if you inscribe a circle in a square, the area of the circle is $\pi r^2$ and the area of the square is $4r^2$, so the probability of being in the circle is $\frac{\pi}{4}$. This is completely exact, but you pay the price that some of the queries for "are you in the circle?" will take a very long time. – Ian Dec 16 '15 at 00:24
  • But the probability of being in, say, a floating point double precision version of the circle is not truly irrational, it is just a rational number which probably can only be written using a huge denominator. That's because the floating point circle is not really a circle, it is more like a polygon with a huge number of sides. – Ian Dec 16 '15 at 00:26
  • @Ian Agreed. As I say, I'm not sure what "without irrational numbers" means in this context. The process I describe converges to the Bernouilli process with probability $\frac {\pi}4$ as precision increases. Perhaps that isn't satisfactory here. – lulu Dec 16 '15 at 00:26
  • @Ian, though, to be clear, the "in the circle" question I am asking is really just "is $x^2+y^2≤\frac 14$". I am not using the geometric circle at all. – lulu Dec 16 '15 at 00:28
  • @lulu I know. But the solutions to x^2+y^2<=r^2 in floating point make a polygon (or rather, a collection of dots which all lie in some polygon). On the other hand, the arbitrary precision calculation of $x^2+y^2 \leq r^2$ could take a long time, depending on $x$ and $y$. – Ian Dec 16 '15 at 00:30
  • @Ian. Agreed. The "lattice circle" is really a polygon. – lulu Dec 16 '15 at 00:33

3 Answers3

3

We start with a unit square $[0,1]\times [0,1]$ In each iteration we divide the square in four, we generate a pair $(X_n,Y_n)$, where the components are iid Bernouli with $p=1/2$, and we select one of the four sub-squares according with the result. We stop whenever the current square does not intersect the unit circle. We output $Z=1$ if the final square is inside the circle, $Z=0$ otherwise.

So, we've generated, using only rational operationts, a Bernoulli with $P(Z=1)=\pi/4$. The number of iterations is unbounded, true, but the average is finite.

A similar and simpler way, in one dimension, dividing the unit segment and stopping when the extremes squared are both smaller or greater than $1/2$ generates a Bernoulli with $p=1/\sqrt{2}$

leonbloy
  • 63,430
  • How exactly do you detect that a square does not intersect the circle using only rational operations? I don't think the closest point to the center is always in some corner (which would be the easy way out). – Ian Dec 16 '15 at 00:44
  • @Ian You evaluate $x^2+y^2$ for the "inner" corner ($r^2_{SW}$) and for the outer corner ($r^2_{NE}$). The square intersects the circle iff $r^2_{SW}<1$ and $ r^2_{NE}>1$ – leonbloy Dec 16 '15 at 12:56
2

Randomly generate the digits of a binary representation of a number between 0 and 1, and stop when the expansion certifies the number as being above or below a given threshold $p$. Output 1 if below and 0 if above.

The output is 1 with probability $p$.

This method is attributed to von Neumann.

zyx
  • 35,436
  • I'm not sure but the last line says the OP wants to be able to run this as a program. Would such a program have the possibilty of being non-ending? Or maybe I'm not understanding or making assumptions. – fleablood Dec 16 '15 at 00:23
  • How would I do this if I wanted a probability of sqrt(2) - 1 for example? What would the threshold be? When would it return 0, when would it return 1? – Fricative Melon Dec 16 '15 at 00:24
  • @user1657355 Getting you started: the first few digits of sqrt(2)-1 are 0.0110. So if your first digit is $1$, your number is bigger, so you return 0. Otherwise if your second digit is 0, then your number is smaller, so you return 1. Otherwise if your third digit is 0, then your number is smaller, so you return 1. Otherwise if your fourth digit is 1, then your number is bigger, so you return 0. And so forth. But to make this be guaranteed to work you need a way to compute the digits of the number on demand. – Ian Dec 16 '15 at 00:43
  • @fleablood, with probability 1 the program will stop. – zyx Dec 16 '15 at 00:53
  • 1
    Slightly more generally, rather than being able to compute the digits we can get by with an algorithm to compute arbitrarily close rational approximations: e.g. say $f(n)$ is a rational with $|p - f(n)| < 1/n$. Stop when the current number differs from $f(n)$ by more than $1/n$ (again, with probability $1$ this will happen eventually). – Robert Israel Dec 16 '15 at 01:05
0

In the case of a quadratic irrational $p=q+\sqrt{s}$, where $q$ is a rational number, $s$ is a positive rational number, and the overall quantity is between $0$ and $1$, you can sample a random variable which is $1$ with probability $p$ and $0$ with probability $1-p$ as follows. Suppose $B_k$ are iid Bernoulli(1/2) variables. Introduce $x_n=\sum_{k=1}^n 2^{-k} B_k$ and $x_\infty = \lim_{n \to \infty} x_n$. Then $x_\infty$ is uniformly distributed in $[0,1]$. So you want to return $1$ if $x_\infty \leq p$ and otherwise return $0$.

Here's the key point: $x_n>p$, then $x_\infty>p$. On the other hand, if $x_n+2^{-n} \leq p$, then $x_\infty \leq p$. The truth value of these inequalities can be detected by using a quadratic with rational coefficients which has a root at $p$. One of these is $x^2-2qx+q^2-s$. So if $x_n^2-2qx_n+q^2-s>0$, then you return $0$. If $(x_n+2^{-n})^2-2q(x_n+2^{-n})+q^2-s \leq 0$, then you return $1$. Otherwise you get another digit and repeat. The process terminates with probability $1$.

Ian
  • 101,645