# I Choosing a Random Number

1. Apr 17, 2017

### PeroK

Here's a challenge of sorts, inspired by some previous discussions.

You must choose a random number uniformly on the interval $[0, 1]$. If the number is rational, someone wins a £1 million prize. If the number is irrational, no prize is won.

It is your task to devise the method by which the random number is chosen and checked for rationality. All numbers between $0$ and $1$ must have an equal probability (density) of being chosen.

What we know from probability theory is that the probability of a rational number being chosen is 0, but that it is still "possible", in some sense.

My belief is that the challenge is impossible, although I am happy to be proved wrong.

2. Apr 17, 2017

### Buzz Bloom

Hi PeroK:

I think there are some conceptual issues with your question.

(1) How do you define "select a random number?
(2) How is the selected random number identified so that it can be tested for whether of not is is rational?

There are likely to be other conceptual issues which depend on how you answer these two questions.

Regards,
Buzz

3. Apr 17, 2017

### PeroK

(1) and (2) are what the method has to establish. I don't really see any conceptual issues. I see practical issues.

4. Apr 17, 2017

### AplanisTophet

The "odds" of chosing a rational in this case are, to the best we are able to (currently) define, 0, however, the irrationals can be mapped uniformly to the rationals, so if the contest allows for the selection of a rational by

1) randomly selecting it, or
2) randomly selecting a rational equal to f(x) where f is a uniform mapping of the irrationals in [0, 1] to the rationals in [0, 1],

then I suppose it could be done.

Now, I assume people will say, "hey, there is no uniform mapping of the irrationals on [0, 1] to the rationals on [0, 1]." To that, I say see https://www.physicsforums.com/threads/selecting-a-natural-and-a-real-uniformly-at-random.911544/

I'm looking for clarification myself.

5. Apr 17, 2017

### Buzz Bloom

Hi
Hi PeroK:

Just for the sake of discussion I assert that there is NO practical way to "select a random number" from the set of reals, say limited to reals between zero and one.
Do you dispute that? If so, what argument, if any, do you offer?

Regards,
Buzz

6. Apr 17, 2017

### AplanisTophet

Great point.

My take is that if we want to assert both the axiom of infinity (implying the existence of the natural numbers) and our ability to flip a coin (function $f$), then we should be able to assert the existence of an infinite binary sequence $S = s_1, s_2, s_3, …$ where each element of the sequence is selected randomly: $f(n) = s_n$.

7. Apr 17, 2017

### PeroK

I agree with that. I think even (1) is impossible. But, in another thread, we have a suggestion to use a dartboard.

I think that "let X be a random variable distributed uniformly on [0,1]" makes sense mathematically. But, I'm not convinced that it can be applied to reality. The Internet is full of (attempted) serious applications of probability theory that involve choosing a random number like this. But, if you can't actually do it, then it's meaningless. You have to remain in the abstract realm of mathematics.

8. Apr 17, 2017

### TeethWhitener

I'm guessing that determining whether a random number $\in [0,1]$ is rational or irrational will end up being equivalent to the halting problem, and therefore undecidable. "Is it rational?" is basically "Does it halt or repeat?" which is pretty close to "Does it halt?" in my book.

9. Apr 17, 2017

### PeroK

Yes, after I posted the question, I began to wonder about that too.

10. Apr 17, 2017

### TeethWhitener

In fact, I'm almost certain it is: a number $n \in [0,1]$ is rational iff $nk \in \mathbb{N}$ for some natural number $k$. A test for rationality would be equivalent to:
Code (Text):
Multiply n by k
if n*k is a whole number then
halt
else
k = k++
This is pretty much the exact setup for the halting problem.

11. Apr 17, 2017

### AplanisTophet

Every rational will have a finite expansion in some base (e.g., dyadic rationals have a finite binary expansion).

Without a finite expansion, I don't see how a computer could even compute n*k much less get to the k++ part, as long as we're being "practical." By the time you know whether the number has a finite expansion in some base, you have your answer.

Is checking whether the number has a finite expansion in some base equivalent to the halting problem too?

12. Apr 17, 2017

### SlowThinker

The true challenge here is, how do I tell you which number I selected? Most of them, 100%, require infinite amount of information to be described.

13. Apr 17, 2017

### SSequence

There is a straight-forward mapping (total and onto but not 1-1) from the set N to the set of all reals with computable decimal representations. Here is how it goes. For example, first treat the given input (say x) as an index to a program. Assume a 1-1 correspondence between N and the set of programs (which should be easy to establish) ...... or at least an onto mapping. Denote the function computed (by program with index x) as f: N→N. Now if for example we had:
f(0)=15, f(1)=10, f(2)=12, f(3)=14, f(4)=6 .....
convert it to:
g(0)=15, g(1)=10%10=0, g(2)=12%10=2, g(3)=14%10=4, g(4)=6%10=6,......
So the corresponding real number is:
15.0246....

What if the function f computed by the program was partial? Well in that case we can assume a string of 0's starting from the smallest point from which f was partial. For example, in the above case if f(5) was undefined/partial then the corresponding real number would be:
15.02460000000000....

Now one can ask that whether it is decidable/recursive whether when we select a given number as input, can we decide whether the real that the input selection is supposed to represent is rational or not. By rice's theorem the answer is no (demonstrated by giving simple example of two separate programs, one whose function corresponds to some rational number and one whose function corresponds to some irrational number).

==========

But the actual question is of selecting an arbitrary real. Now taking the point of real numbers as uncountable, by the very definition we have no correspondence function from N to the reals. But I think that one may perhaps set certain properties that would hold after finite number of arbitrary selections as such. Don't know how useful it would be though.

Last edited: Apr 17, 2017
14. Apr 17, 2017

### Stephen Tashi

How are we measuring "information"? $\$ Is "$\sqrt{2}$" an infinite amount of information?

15. Apr 17, 2017

### TeethWhitener

@SlowThinker and @SSequence bring up an important point, namely that the computable numbers are countable. It might be more interesting to restrict one's attention to the set of computable numbers between 0 and 1. Is there an efficient algorithm to determine, from this restricted set, whether a given number is rational or irrational? I honestly have no idea.

16. Apr 17, 2017

### Stephen Tashi

A mathematical model like "let X be a random variable distributed uniformly on [0,1]" could be useful even if it is physically impossible to implement. It could be useful as an approximation to situations that are physically possible.

I'm not sure that it is physically possible to select a random number from a uniform discrete distribution on {1,2,...9, 10}, but let's assume it is. We could use that process to approximate sampling from a uniform distribution on [0,1] to a given "granularity" in stages by picking one of 10 equal length subintervals of [0,1] and then picking a sub-subinterval of that subinterval etc.

Suppose we have a problem, whose answer $A(\epsilon)$ is a function of $\epsilon$, the smallest length interval we use. We can define a "limiting answer" as $A = \lim_{\epsilon \rightarrow 0} A(\epsilon)$ when such a limit exists.

It may be that the answer $A$ can be computed by manipulations involving the assumption that we take samples from a uniform distribution on [0,1] instead by computing the answer for a finite $\epsilon$ and then taking a limit. In such a situation, the practical value of using the continuous model depends first on whether the "limiting answer" $A$ has any practical significance and second on whether the manipulations using the uniform distribution simplify calculations.

My first impression is that theoretical questions like "What is the probability that a number selected from a uniform distribution on [0,1] is an irrational number?" can't be formulated as a "limiting answer" to a sequence of finite approximations. But less theoretical questions like "What is the distribution of the mean of N samples from a uniform distribution on [0,1] ?" could be.

17. Apr 17, 2017

### AplanisTophet

"Odds" are, we're talking about an infinitely long string of numbers in any base. Yeah, it's abstract and theoretical in most every sense of those terms. Focusing on computable numbers only is off topic and trying to assert that a computer could determine after a finite number of steps whether the number repeats or terminates in any base 'every time' so as to avoid the halting problem is just not going to happen.

If a computer can load the number into its memory so to speak in any given base, then just as you give a mouse a cookie it can in any base, so we're done. A finite expansion in any base means it's rational and if none exists, it's not. Yeah, the halting problem could easily be asserted here as "practically" (not sure the mathematical context of that word) we can't wait around to see if our computer program halts or not. We're done. You either have to acknowledge a trip into the theoretical like a mathematician or stick to reality like a physicist (pardon my rudeness please), your choice.

18. Apr 17, 2017

### TeethWhitener

"Computable" in this context has a precise mathematical definition. It's not based on whether an actual physical computer can store it in memory.
https://en.m.wikipedia.org/wiki/Computable_number

19. Apr 17, 2017

### Stephen Tashi

In base 10, the infinite expansion 0.333... is a rational number.

One could use $\sqrt{2}$ as the base and express some irrational numbers as finite expansions.

20. Apr 17, 2017

### AplanisTophet

Yes, but the OP was to select a number randomly in [0,1], not a computable number.

21. Apr 17, 2017

### AplanisTophet

Yes, but in base 3 it's got a finite expansion. No need for 'infinite' memory as is the case with all rationals.

The OP is to find a rational, not some number in an irrational base.

22. Apr 18, 2017

### SSequence

As I described in the previous post, that under a reasonable (total and onto) mapping from N to reals with computable decimal representations, the problem is not decidable/recursive.
Here a reasonable mapping means that you can write a simple program so that given any number as input, the program determines the corresponding real to arbitrary precision (in sequential/non-terminating sense).

There is also a somewhat related but separate problem. You could be given a program/function f as a blackbox essentially and "already" told that its total. Then your task is to determine whether it represents a rational or not. But I think that it would be extremely likely (though I haven't tried to look at the reasoning) that this is not amenable to any uniform algorithm (in terms of the given function f) either.

But seemingly, non-recursive sets don't necessarily preclude a notion of probability. I think this would become a little context dependent then probably. The following might be of some interest (I happened to have glanced it few years ago but haven't really read it):
https://projecteuclid.org/euclid.ndjfl/1168352664
Looking very briefly, I think the part about probability of FIN is probably relevant here (page 6 of 10).

==========

Also I think there is a general issue with how to make an "unpredictable" selection. If someone told you to make a selection (based upon a fixed indexing such as above) and the selection program always started from 0 fresh, the selection would hardly be unpredictable. If however, the program kept/stored a counter and never resetted it (instead only incremented it) then it would be different.

Last edited: Apr 18, 2017
23. Apr 18, 2017

### PeroK

Thanks to everyone who replied. As I suspected, the challenge as stated is not practical and perhaps for more reasons that I originally anticipated.

24. May 1, 2017

### sysprog

There is no atomic distance on a numeric interval, except by definition the infinitesimal.

When we try to select a number from within the interval from 0 to 1 at random, we cannot determine what number we have selected, unless it is numerically determinate, and therefore not irrational.

If our selection is proving to be non-determinate, we cannot legitimately be said to have selected a number, unless we have a non-numeric name for some irrational part of the number as specified, e.g. Φ/5 would be an irrational number within the interval.

If only rational numbers can be definitively selected, the selection is 100% non-random vis-a-vis rational vs irrational.

If our set of choices is allowed to include a named irrational number, e.g. Φ, divided by a rational number > Φ so as to keep the result within the interval, we could choose a qualified rational number X at random, then choose at random with 50% probability whether to divide Φ by it or instead divide it by another rational number chosen at random from numbers > X so that the resulting fraction would be within the interval, and would be a random number with equal probability of being a rational or irrational number ...

Last edited: May 1, 2017
25. May 1, 2017

### FactChecker

A number can be selected without giving it a name. There is a significant difference between selecting a number and naming or even identifying it. If it exists, it can be selected.