- #1

Stephen Tashi

Science Advisor

- 7,545

- 1,456

The theory of computability deals with mathematically possible and impossible things within an abstract framework. Has anyone has ever worked out what happens when it meets probability theory?

I have some questions and musings about that.

It is common in probability theory to talk about taking a sample from a continuous random variable, such as the uniform distribution on [0,1]. Probability theory just assumes you can do it and proceeds to analyze the consequences. But can it really be done?

First, is it physically possible? Can Nature can do it? I see nothing in Quantum Mechanics that forbids it. In fact, it seems to me that Quantum Mechanics uses some continuous probability distributions (Please orrect me, if I'm wrong.). However,if Nature does it, our ability to measure the outcomes is limited by their precision. So I don't think it is physically possible for beings to create a process that samples from a uniform distribution over all in the numbers in the interval [0,1].

Next, is it mathematically possible? Let's think about this in terms of whether some computer algorithm exists to do it. I suspect not, even if we allow the algorithm to have some external "random" input of finite precision..

I also suspect that proving this impossibility is tricky. For example, you can't claim "computers only represent rational numbers" because computers can manipulate symbols. An irrational number can be represented as a symbol like [itex] \pi [/itex] and an algorithm can generate symbolic expression like [itex] \sqrt{\pi} [/itex] or [itex] \pi^\pi[/itex]. Perhaps an argument based on cardinality would do.

When the status of solving problem X in computability theory is unknown, it is still of interest to prove theorems that say "If we had a way to compute an answer to problem X then we could compute an answer to problem Y".

If we could take a random sample from uniform distribution on the rational numbers in [0,1] then we could take a random sample from a [in some sense] uniform distribution on the positive integers. We know there are methods of making a 1-to-1 mapping between the rational numbers in [0,1] and the positive integers. You could pick your rational number "at random" then find out what integer it mapped to.

I don' know what measure theory has to say about this. I don't detect anything in measure theory that assumes computability. Measure theory would frown on claiming we have created a uniform distribution on the positive integers that gives each integer the same nonzero probability p of being selected. However, a uniform distribution on the rationals in [0,1] doesn't assign a nonzero probability to any individual rational number, so it isn't assigning a nonzero probability to the corresponding integer.

I don't think such a uniform distribution on the integers would provide answers to questions like "what is the probability that an integer selected at random is even?". There are many different ways to match the integers to the rationals. For example, you could count through the integers by listing two 2 odd integers followed by 3 even integers, like { 1,3, 2,4,6,5,7,8,10,12,...}. I don't see why all these ways would lead to the same answer and I'm not sure "the set of even integers" would be a measureable set.