# Is randomness provable?

1. Jun 27, 2010

### mt8891

the subject is all there is to it. I mean, is randomness a provable property of the integers? can there be such thing as a random integer? to me it seems no IF the "one way function" theorem is disproved. at the same time, what about those wacky isotopes from half lives, ie schrodinger. whats the deal?!?!

2. Jun 27, 2010

### rasmhop

What does this mean? I don't see how this makes any sense. It's not really meaningful to ask whether the integers are random.

That depends on what you mean by a random integer. An integer is a particular one. You can't have an integer that is 50% 1 and 50% 3. However what you can have is a random variable taking values in the integers. For instance we may have a random variable X that has a 50% chance of being 1 and a 50% change of being 3. However formally we can merely interpret X as a function from [0,1] to the integers such that X(w) = 1 if w < 0.5 and X(w) = 3 otherwise. There is nothing random, but if you choose a random number (uniformly) in [0,1] you can use that and the random variable function to choose either 1 or 3 with probability 50% each.

These sorts of formal constructions are formalized in probability theory. A lot of it depends on mapping [0,1] into a space to determine how likely something is. In the discrete case we may instead map something like {1,2,3,4} into a set to determine probability. For instance we may assign 25% probability to 1, 2, 3 and 4. To determine a random color we may map 1 and 2 into "Red", 3 into "Green" and 4 into "Blue". Then we say that there is 50% chance of getting red, 25% of green and 25% of blue. This is all randomness is to mathematicians. I may instead have said that 1 have 50% probability, 2 have 10%, 3 have 40% and 4 have 0%. Then we have 60% of getting red, 40% of getting green and 0% of getting blue (We're changing the underlying probability space which describes the probabilities of different events). We do not need to demonstrate that such randomness occurs in real life. We just postulate its existence and reason about the effects given some formal rules. If physicists feel our system model real-life they can use it, but math makes no guarantee that it has anything to do with how randomness works in the real world. In high school you may assume that a dice thrown will randomly result in one of 6 values, but in reality we may be able to calculate the outcome from how it's thrown. Maybe there is a 100% change of it being 4 if you just observes the hand throwing it carefully enough.

I haven't heard of this before. I looked it up and it seems the "one way function" theorem is a conjecture stating that a one way function exists. However I'm not sure what this has to do with randomness. If you feel it's important would you mind giving a short explanation of what this is and why it has any impact on randomness?

This is about physics not mathematics. In mathematics we sometimes work with systems that are hard to think of as the model of something physical. For instance we have numbers larger than the number of objects in the universe (assuming some discreteness of objects and finiteness of the universe). Even if the universe is deterministic and nothing is truly random we can still work with what mathematicians call randomness as long as we work with formal systems. I have no idea whether randomness exists in the universe, but we can certainly model it mathematically.

3. Jun 27, 2010

### skeptic2

I wonder if the OP was asking whether given a sequence of numbers of indefinite length, can that sequence be proven to be random?

4. Jun 27, 2010

### rasmhop

If that was the case then again what does it mean for a sequence to be random? Is (2,3,4) random? If what is meant is to determine whether the sequence was generated randomly, then of course you can't determine that. If I tell you the sequence
2,4,6,...
of even positive integers you can't tell whether it was randomly generated or I just listed the even positive integers in order.

Of course as with integers you can create a random variable that returns different sequences with different probabilities.

5. Jun 28, 2010

### zetafunction

well perhaps, you CAN

for example a 'brownian motion' is a random procedure that appears in nature, if you would like to say if a sequence is at RANDOM you could fit and check if the sequence satisfy a Brownian motion.

6. Jun 28, 2010

### HallsofIvy

There is no such thing as a "random integer". Once you have an integer, it is not random! There is such a thing as a collection of "randomly chosen" integers- that is, it is how they are chosen that is random, not the integers themselves. Also, there are many different defining "random". In order to prove that method of choosing integers or any other objects is "random" you would first have to specify your definition of "random".

7. Jul 2, 2010

### mt8891

alright to expand on this a little bit....

the other night a question was presented:

given that there is a one-fourth chance of getting disease X for one parent...ie if one parent has X then there is a 1/4 chance that any offspring has X...then..what are the conditions that it goes to zero. ie(X dies off an no offspring have X)

so I tried making a chart with a die and all that but eventually the whole point of the question was lost and I was more curious about some of the results I found. here is what happened that made me interested (plus some barley and hopps and a book on real analysis)..well this is what I thought would be good to do anyway but....

firstly; I tried rolling a die but I added a zero..whatever...the second time I used the numbers I got and tried to stay true to my die rolls.what I came up with is:

I rolled the die and got a n.
then I rolled the die n times... and got a n
then I rolled the die n times and got a n
(...)

I just considered the number of `("primes") the 'generations then' :

e^(generation + 1)

was pretty close to

the sum of the die rolls of each successive generation and so fourth.

I then wrote a program to simulate this but it only calculated 0 - 5..am currently trying to work out the kinks. but yeah...

the whole deal just got me curious about "randomness" and probability..

8. Jul 5, 2010

I'm not sure you can prove a sequence of numbers to be (pseudo)random as I think this problem might be related to the notion Kolmogorov complexity.

Almost always the approach is to try assiduously to prove the sequence does not measure up to a given set of criteria or randomness tests for a pseudorandom sequence of numbers.

There are varyingly stringent sets of criteria and randomness tests depending on how exigent you are. If you fail then you can say you are not(reasonably) satisfied the sequence is close enough to random.

One of the places most people and PseudoRNGs go wrong is not bounding the length and the width (range of possible values) of the pseudorandom sequence before generating. This leads to innate problems like periodicity, sequences which are not uniformly distributed, value climbing (it is more likely the next number in the sequence will be larger than the mean so far), etc.

Randomness is less meaningful the shorter the sequence becomes because it gets increasingly difficult to prove the sequence is not random output.

One relatively easy (difficult to implement) way I've tried to generate pseudorandom numbers is from the decimals of irrational numbers.