Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Choosing a Random Number

  1. Apr 17, 2017 #1

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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. jcsd
  3. Apr 17, 2017 #2
    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
     
  4. Apr 17, 2017 #3

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    (1) and (2) are what the method has to establish. I don't really see any conceptual issues. I see practical issues.
     
  5. Apr 17, 2017 #4
    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.
     
  6. Apr 17, 2017 #5
    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
     
  7. Apr 17, 2017 #6

    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 [itex]f[/itex]), then we should be able to assert the existence of an infinite binary sequence [itex]S = s_1, s_2, s_3, …[/itex] where each element of the sequence is selected randomly: [itex]f(n) = s_n[/itex].
     
  8. Apr 17, 2017 #7

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  9. Apr 17, 2017 #8

    TeethWhitener

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  10. Apr 17, 2017 #9

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, after I posted the question, I began to wonder about that too.
     
  11. Apr 17, 2017 #10

    TeethWhitener

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  12. Apr 17, 2017 #11
    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?
     
  13. Apr 17, 2017 #12
    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.
     
  14. Apr 17, 2017 #13
    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
  15. Apr 17, 2017 #14

    Stephen Tashi

    User Avatar
    Science Advisor

    How are we measuring "information"? ##\ ## Is "##\sqrt{2}##" an infinite amount of information?
     
  16. Apr 17, 2017 #15

    TeethWhitener

    User Avatar
    Science Advisor
    Gold Member

    @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.
     
  17. Apr 17, 2017 #16

    Stephen Tashi

    User Avatar
    Science Advisor

    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.
     
  18. Apr 17, 2017 #17
    "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.
     
  19. Apr 17, 2017 #18

    TeethWhitener

    User Avatar
    Science Advisor
    Gold Member

    "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
     
  20. Apr 17, 2017 #19

    Stephen Tashi

    User Avatar
    Science Advisor

    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.
     
  21. Apr 17, 2017 #20
    Yes, but the OP was to select a number randomly in [0,1], not a computable number.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Choosing a Random Number
  1. Random Number (Replies: 0)

  2. Random numbers timed (Replies: 1)

Loading...