- Joined
- 26 Apr 03
- Moves
- 26771
This is a tricky one following on from another thread .. any suggestions to a method are welcome - as I have no idea!
You want to generate a random integer - is there any way of doing this that will give an equal probability of generating all possible integers?
You can assume the existence of a method to generate a flat distribution of random integers within any finite range.
It can't be done, because of the following rules in probability theory:
-the sum of probabilities of disjunct events (two events are disjunct if they can't both happen at the same time) equals the probability of the happining of one of the events.
-if all events are disjunct, then the sum of probabilities of all events equals 1.
If the probability of P(X=1) > 0, say P(X=1) = t, then P(X=<n) = nt for all n.* Then for n large enough, nt > 1. But P(X=<n) < P(X=<inf) = 1. Therefor P(X=1) must equal 0. But then P(X=<n) = 0 for all n. But then 1 = P(X<inf) = lim P(X=<n) = 0. So there exists no probability space in which you can choose a random integer
*because P(X=<n) = sum{k in 1..n} P(X=k) = sum{k in 1..n} P(X=1)=n*P(X=k)=nt
Originally posted by Fiathahel*laughs* I knew the subject was good for something!
It can't be done, because of the following rules in probability theory:
-the sum of probabilities of disjunct events (two events are disjunct if they can't both happen at the same time) equals the probability of the happining of one of the events.
-if all events are disjunct, then the sum of probabilities of all events equals 1.
If the probabili ...[text shortened]... eger
*because P(X=<n) = sum{k in 1..n} P(X=k) = sum{k in 1..n} P(X=1)=n*P(X=k)=nt
- Joined
- 26 Apr 03
- Moves
- 26771
Originally posted by FiathahelInteresting - does that mean Mr. R Chicken's question about the probability of randomly selecting a rational number with an even denominator is meaningless, because there is no way to select such a random number?
It can't be done, because of the following rules in probability theory:
-the sum of probabilities of disjunct events (two events are disjunct if they can't both happen at the same time) equals the probability of the happining of one of the events.
-if all events are disjunct, then the sum of probabilities of all events equals 1.
If the probabili ...[text shortened]... eger
*because P(X=<n) = sum{k in 1..n} P(X=k) = sum{k in 1..n} P(X=1)=n*P(X=k)=nt
Say you had a (probably analogue) method of obtaining a real number between 0 and 1 - could you then use such a real number to obtain a real number between 0 and infinity - and then take the nearest rational to that real? Does an operation exist which will scale the real number suitably without destroying the flatness of the original random distribution?
Originally posted by iamatigerYes, if you can't choose an integer random, you can't choose a rational random.
Interesting - does that mean Mr. R Chicken's question about the probability of randomly selecting a rational number with an even denominator is meaningless, because there is no way to select such a random number?
Say you had a (probably analogue) method of obtaining a real number between 0 and 1 - could you then use such a real number to obtain a real ...[text shortened]... le the real number suitably without destroying the flatness of the original random distribution?
With reals you have the same problem. If you look at the events n=<X<n+1, then you got a countable set of disjunct event. Then you got the same problem as before.
- Joined
- 26 Apr 03
- Moves
- 26771
Originally posted by FiathahelWell, I think I can choose a random real within finite limits - eg by tossing a stick onto the floor and representing the real by the angle it is pointing at. What's wrong with that method apart from being a little slow?
Yes, if you can't choose an integer random, you can't choose a rational random.
With reals you have the same problem. If you look at the events n=<X<n+1, then you got a countable set of disjunct event. Then you got the same problem as before.
Originally posted by iamatigerOh, sure, if it's finite it is (in theory) possible. Only when it is infinite you got a problem. You can use the lebeque-measure (standard measure on the reals, that gives for example that the probability of X being in an interval equals a constant times the interval length). Like you do when throwing that stick.
Well, I think I can choose a random real within finite limits - eg by tossing a stick onto the floor and representing the real by the angle it is pointing at. What's wrong with that method apart from being a little slow?
- Joined
- 26 Apr 03
- Moves
- 26771
Originally posted by FiathahelCan't I then somehow scale the angle represented by that stick to a random range - For instance I can geometrically represent the Tan of the angle without destroying its realness - and the Tan gives me all possible reals - not with equal probability though...
Oh, sure, if it's finite it is (in theory) possible. Only when it is infinite you got a problem. You can use the lebeque-measure (standard measure on the reals, that gives for example that the probability of X being in an interval equals a constant times the interval length). Like you do when throwing that stick.
Look, my question about "choosing" a random rational is acceptable, because It assumes that in principal it can be done. The "probability" of a natural number having some property is merely the asymptotic density of the numbers having that property. For example, since there are [sqrt(N)] = sqrt(N) + O(1) squares less than N, the formal probability of randomly selecting a square is lim (N->inf) 1/sqrt(N) = 0.
From any FINITE set of naturals, the probability of selecting a square is about 1/sqrt(N) if N is the largest number in the set.
So all my question asks is what the density of even-denom rationals is in the rationals, which is 1/3.
As to generating random reals, note that the good idea of taking a random real from [0,1] and then taking its reciprocal doesn't really help the "taking a random element from an infinite set" problem, since [0,1] and R have the same cardinality. But I think you know this.
I don't think it is meaningful to talk of "selecting at random from a set" in terms of actual methods, because I challenge one of you to "randomly" select an integer from {1,2,3}.
The real measures of randomness occur in measuring the degree to which a set's statistical properties correspond to those of some distribution. For example, a very simple test of how "random" a finite set of integers is is to merely count the number of evens in it and see if they duplicate the theoretical frequency of 1/2.
I have had some idea recently about measuring the "randomness" (or, since it is equivalent), amount of information provided by, finite sets of natural numbers (NOTE TO ACOLYTE: The goal is to prove a hardcore strong version of van der Waerden's theorem). Interestingly, the measure I have come up with corresponds closely to the conept of thermodynamic entropy that my physics teacher was so fond of haarping on. If anyone's interested, I might post them in all their beautiful incompleteness.
Originally posted by AcolyteAcolyte, I have very poor depth perception, and it's doubtful I'd be able to hit the ground with a stick thrown from arm level. Furthermore, the chance of my stick intersecting the "given line" is miniscule 😛.
There are of course ways of generating a random real number non-uniformly; for example, toss the stick on the ground and take the tangent of the angle it makes with a given line.