Random Integer

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
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

*laughs* I knew the subject was good for something!

Originally posted by Fiathahel
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

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 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 iamatiger
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?

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=&lt;X&lt;n+1, then you got a countable set of disjunct event. Then you got the same problem as before.

Originally posted by Fiathahel
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.

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?

Originally posted by iamatiger
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?

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.

Originally posted by Fiathahel
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.

Can'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...

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.

You can also take any distribution of X on [0,1], and then look at 1/X

I just love Dutch logic.......🙂

Olav

Originally posted by LivingLegend
I just love Dutch logic.......🙂

Olav

and women's logic of course ... 🙄

Look, my question about &quot;choosing&quot; a random rational is acceptable, because It assumes that in principal it can be done. The &quot;probability&quot; 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-&gt;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 &quot;taking a random element from an infinite set&quot; 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 &quot;selecting at random from a set&quot; in terms of actual methods, because I challenge one of you to &quot;randomly&quot; 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 &quot;random&quot; 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 &quot;randomness&quot; (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 Acolyte
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.

Acolyte, 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 &quot;given line&quot; is miniscule 😛.

I'd take a bunch of numbers and throw them in a hat... I would also hope royalchicken had the skill to reach in said hat and remove a singe number......

Math that out!

Phla-

ps. More numbers?? Bigger Hat!