1. Joined
    26 Apr '03
    Moves
    25837
    01 Sep '03 11:491 edit
    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.
  2. Standard memberFiathahel
    Artist in Drawing
    in your fridge
    Joined
    21 May '03
    Moves
    9766
    01 Sep '03 13:16
    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

  3. Standard memberTheMaster37
    Kupikupopo!
    Out of my mind
    Joined
    25 Oct '02
    Moves
    20443
    01 Sep '03 14:42
    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!
  4. Joined
    26 Apr '03
    Moves
    25837
    01 Sep '03 15:45
    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?
  5. Standard memberFiathahel
    Artist in Drawing
    in your fridge
    Joined
    21 May '03
    Moves
    9766
    02 Sep '03 07:09
    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.

  6. Joined
    26 Apr '03
    Moves
    25837
    02 Sep '03 07:461 edit
    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?
  7. Standard memberFiathahel
    Artist in Drawing
    in your fridge
    Joined
    21 May '03
    Moves
    9766
    02 Sep '03 11:54
    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.
  8. Joined
    26 Apr '03
    Moves
    25837
    02 Sep '03 13:03
    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...
  9. DonationAcolyte
    Now With Added BA
    Loughborough
    Joined
    04 Jul '02
    Moves
    3790
    04 Sep '03 12:30
    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.
  10. Standard memberFiathahel
    Artist in Drawing
    in your fridge
    Joined
    21 May '03
    Moves
    9766
    04 Sep '03 12:45
    You can also take any distribution of X on [0,1], and then look at 1/X
  11. Amsterdam
    Joined
    26 Jan '03
    Moves
    27540
    04 Sep '03 15:55
    I just love Dutch logic.......🙂

    Olav
  12. Felicific Forest
    Joined
    15 Dec '02
    Moves
    26462
    04 Sep '03 17:54
    Originally posted by LivingLegend
    I just love Dutch logic.......🙂

    Olav


    and women's logic of course ... 🙄

  13. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    04 Sep '03 20:11
    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.
  14. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    04 Sep '03 20:13
    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 😛.
  15. Standard memberPhlabibit
    Mystic Meg
    tinyurl.com/3sbbwd4
    Joined
    27 Mar '03
    Moves
    17242
    05 Sep '03 05:00
    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!
Back to Top