Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider a computer program that generates any random number between 0 and 1(exclusive). There are infinitely many numbers between 0 and 1. So the probability that the random-number generate the same number twice, will be given by -

$P(E)={1\over \infty}=0$
($\because$ number of favourable outcome = 1, sample space = $\infty$)

But it has happened many times that the program repeats a number, even though, the probability of that event is 0.

Please explain this.

share|improve this question
4  
The whole number-of-favorable-outcomes-devided-by-number-of-elements-of-sample-space approach to probability makes only really sense for finite probability spaces and is even there overly restrictive. –  Michael Greinecker Jan 28 '13 at 13:48
3  
You do not even need look for repeated numbers -- the probability of generating any given number is zero (assuming a true random-number generator and infinite precision). Still it happens every time the generator is run. –  Ansgar Esztermann Jan 28 '13 at 14:02
2  
Consider a computer program that generates any random number between 0 and 1... Simply put, such a thing does not and cannot exist. –  Did Jan 28 '13 at 14:10
4  
You think wrong and I know what you are talking about. Let me suggest you explain what exactly it is you think the Math.Random() thing is proving. –  Did Jan 28 '13 at 14:36
2  
Sandy: if you drop the idea of using a computer, I think your question is valid. It is possible to (hypothetically) have a RNG which chooses uniformly from $[0,1]$, in which case any given outcome would have probability zero. –  Xodarap Jan 28 '13 at 15:36

5 Answers 5

up vote 8 down vote accepted

If the probability of a random variable taking any particular value is $0$, then the sample space must be infinite, and the probability of a repeated value (in a sequence of i.i.d. samples) is also $0$. So if you see a repeated value, you can conclude with confidence that the probability of that particular value is not zero:

  • because the sample space is actually finite, or
  • because the samples are not actually independent, or
  • because the probability distribution is not actually uniform.

On a computer, all of these problems occur at once: there are only finitely many floating-point numbers; pseudo-random number generators do not generate all of these numbers with equal probability; and samples from a pseudo-random number generator are not independent.

share|improve this answer
1  
+1 for all of these problems occur at once... –  Did Jan 28 '13 at 23:20

A real number representation in computers is not really "real". It is represented by a finite number of bits, so only finitely many values can be represented. That means all random variables generated by a computer will be discrete.

share|improve this answer
1  
Besides, even if a computer were able to generate every real number, it couldn't do it completely randomly. In fact, random algorithms are just pseudo-random. –  AndreasT Jan 28 '13 at 13:51
1  
@AndreasT: besides that, even if a computer were able to generate completely random numbers, it couldn't generate every real number. –  Ilya Jan 28 '13 at 14:03
1  
@Ilya: True. But there in fact ARE computer-components that can produce random numbers, some devices are working with radiation, some, like /dev/random on unix-machines, are working with input entropy. But a computer can (but logically not by itself) create random numbers. –  sebigu Jan 28 '13 at 14:17
2  
@SandyLee_user53167 I meant an extension of the Birthday Problem. for example, as it states in the Wikipedia article, the probability of getting a number twice from a uniform sample space of $d$ numbers is above half if you choose around $\sqrt{2d\ln 2}$ numbers, so if you get random 32-bit numbers, you should expect to see repetitions after choosing 100,000 numbers or so. –  Alfonso Fernandez Jan 28 '13 at 15:56
1  
@sebigu This is more of a philosophical / metaphysical question, because you first have to define what "random" really means, and then you have to determine whether the universe is capable of producing such "random" - this is less relevant here though, because even a decent pseudorandom would have a vanishing probability of repeating itself as the 'sample space' gets larger. –  Alfonso Fernandez Jan 28 '13 at 16:07

I must be the world’s worst person to be offering an answer to the question posed in the title, and I will be happy to be slapped down by someone who actually knows probability. But it seems to me that if you want to talk probabilities, you need to specify a probability space, and you need to specify the probability measure on it. Until you do both these things, you are merely talking philosophy, not mathematics.

Consider the example of a unit square $S$ as probability space, and ordinary Lebesgue measure on it, so that the probability of a point being in a subset $A\subset S$ is the area of $A$. Now draw the line from one corner to the opposite corner, and consider this subset $D\subset S$. What is the probability of a point lying on the diagonal $D$? Zero, of course, since a line has zero area. But there are points on the diagonal.

Now, to amplify @Tunococ’s good answer, let me say that one must make a careful distinction between real numbers and computer numbers. There are only a finite number of (floating point) computer numbers in your favorite computer, but uncountably infinitely many real numbers. I once sat in a room where the speaker (correctly) stated that it’s impossible to determine on a computer whether two real numbers are equal, and a Respected Member of the computer science department of my university said “Of course it’s possible: take their difference and see if it’s zero.” But he was wrong. For instance, there’s no way to tell by comparing the numbers on your computer that $\arctan(1/3)+\arctan(1/2)=\pi/4$, even though Pure Thought shows that it’s true.

share|improve this answer
3  
The probability that you are the world's worst person to offer an answer to this question is extremely low. –  Nathan Long Jan 28 '13 at 20:20

An event having probability zero does not mean it is impossible, but that is unlikely to happen. If you look at the qoutients of all pairs of your numbers, and take the quotient of those which are equal by all pairs, for infitite many pairs this quotient will be zero. This means that there are pairs of equal numbers, but there are relatively few.

Another example: Take a pipe. The probability of the pipe breaking at a point is zero, but the probability for breaking might be not zero. If it breakes, it breakes at a certain point. the probability for this was zero, but it happend.

So, finally, probability zero does only mean relatively unlikely, not impossible.

share|improve this answer
    
Even if you know, that a pipe breaks, but you don't have a knowledge where it did break, the probability it have been broken at a particular point is zero. –  Ilya Jan 28 '13 at 14:21

There are number of factors that bound an infinite sample space of a computer program to a finite space:

  1. A number in a computer program has a limited fixed representation. This is limited by the hardware.
  2. Widely used random number generators (such as Random class in C#) produce only pseudo-random sequences. There are real random number generators, but they produce numbers from finite space.

These limitations transforms the equation:

$P(E)={1\over \infty}=0$

To

$P(E)={1\over N}=0$

Where N is a very large positive finite number.

This makes P(E) a very small positive number.


However, if we consider a hypothetical computer in an ideal environment with infinite amount of memory and processing power to compute real random numbers from infinite space. Then, indeed

$P(E)={1\over \infty}=0$

will hold true and you will never see two identical numbers.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.