1. Standard memberFiathahel
    Artist in Drawing
    in your fridge
    Joined
    21 May '03
    Moves
    9766
    31 Aug '03 10:09
    Then i'm curious what proof you got. I still can't imagen it. But we'll see.
  2. Joined
    26 Apr '03
    Moves
    26771
    31 Aug '03 13:20
    Originally posted by royalchicken
    What is the probability that a randomly selected rational number (fraction in lowest terms) has an even denominator?
    The set of rational numers is countable. We can map any rational on to an integer by the following operation (cribbed from http://www.cut-the-knot.org/do_you_know/countRats.shtml):

    Every positive rational number has a unique representation as a fraction m/n with mutually prime integers m and n. Each of m and n has its own prime number decomposition. Let these be

    m = p1^a1 p2^a2 ... pr^ar, and n = q1^b1 q2^b2 ... qs^bs,
    Form the number K(m/n) = p1^(2a1) p2^(2a2) ... pr^(2ar) q1^(2b1-1) q2^(2b2-1) ... qs^(2bs-1).

    K is a function that maps any rational positive number onto a positive integer. A point of note is that K is a 1-1 correspondence.

    Continuing with my own logic:
    If we pick a random integer X and generate its corresponding rational number M/N then we have a good method of randomly selecting a rational number. If X is odd then there will be no powers of 2 in the prime number decomposition of X. So if X is odd N cannot be even.

    If X is even then its prime number composition will contain some power A (A>0) of 2. However a corresponding power of 2 will only appear in the prime number composition of N if A is ODD (if A is even then the power of two will contribute to the prime number decomposition of M).

    So N is odd IF (X is Even) AND (A is Odd)
    the probability is 1/2 * 1/2 = 1/4

    However I suspect I may have gone wrong somewhere, possibly in the assumption that A is randomly ditributed...


  3. Joined
    26 Apr '03
    Moves
    26771
    31 Aug '03 17:01
    Originally posted by iamatiger
    If X is even then its prime number composition will contain some power A (A>0) of 2. However a corresponding power of 2 will only appear in the prime number composition of N if A is ODD (if A is even then the power of two will contribute to the prime number decomposition of M).

    So N is odd IF (X is Even) AND (A is Odd)
    the probability is 1/2 * 1/2 = 1/ ...[text shortened]... may have gone wrong somewhere, possibly in the assumption that A is randomly ditributed...


    Yes, I was wrong - I think the proportion of Odd A's to even A's is 1/2 + 1/8 + 1/32 + 1/128... = 2/3. So the probability of an even denominator is 1/2 * 2/3 = 1/3
  4. Standard memberTheMaster37
    Kupikupopo!
    Out of my mind
    Joined
    25 Oct '02
    Moves
    20443
    31 Aug '03 17:50
    I think you got it right the second time....

    Pick a rational number. The numerator (N) is odd (NO) or even (NE), and the denominator (D) is odd (DO) or even (DE).

    Case 1: NO+DO, Since the denominator is odd, there is no way that simplifying the fraction will result in a even denominator.

    Case 2: NE+DO, Since the denominator is odd, there is no way that simplifying the fraction will result in a even denominator.

    Case 3: NO+DE, That the denominator is even, it means the it's divisible by 2. The numerator isn't, so no matter how much you simplify the fraction, the 2 in the denominator will remain.

    Case 4: NE+DE, Now both the numerator and the denominator are divisible by two, wich means that when you simplify the fraction the 2's will cancel out, wich leaves an odd numerator and denominator.

    Of the four cases, only case 3 has an even denominator. So the ratio even : odd is 1 : 3
  5. Joined
    26 Apr '03
    Moves
    26771
    31 Aug '03 18:042 edits
    Originally posted by TheMaster37
    I think you got it right the second time....

    Pick a rational number. The numerator (N) is odd (NO) or even (NE), and the denominator (D) is odd (DO) or even (DE).

    Case 1: NO+DO, Since the denominator is odd, there is no way that s ...[text shortened]... y case 3 has an even denominator. So the ratio even : odd is 1 : 3
    Thanks for agreeing with me, but I have a few issues with your method : 🙂

    a) One case out of 4 is a prob of 1/4, not 1/3

    b) NE+DE could be something like 2/8 which simplifies to 1/4 (still an even denominator)

    c) I think your method of generating a random number was perhaps biased - if you generate a random numerator and then a random denominator you are stacking the odds because disproprtionately many of your generated numbers will simplify to simple fractions like 1/2.
  6. Standard memberFiathahel
    Artist in Drawing
    in your fridge
    Joined
    21 May '03
    Moves
    9766
    31 Aug '03 23:071 edit
    Can someone proof for me that the probability of picking an even number out of all numbers is 1/2?

    Cause this is what you all use, and this is what I doubt on.
  7. Joined
    26 Apr '03
    Moves
    26771
    31 Aug '03 23:43
    Originally posted by Fiathahel
    Can someone proof for me that the probability of picking an even number out of all numbers is 1/2?

    Cause this is what you all use, and this is what I doubt on.
    Its an interesting question - of course there is exactly one even number for every odd number - so I would have thought that the probability of getting an even number would be 1/2. But can anyone come up with any method at all of randomly (and fairly) selecting an integer when there is no upper or lower bound to the set of integers from which you are to select one?
  8. Standard memberTheMaster37
    Kupikupopo!
    Out of my mind
    Joined
    25 Oct '02
    Moves
    20443
    01 Sep '03 14:28
    Originally posted by iamatiger
    Thanks for agreeing with me, but I have a few issues with your method : 🙂

    a) One case out of 4 is a prob of 1/4, not 1/3

    b) NE+DE could be something like 2/8 which simplifies to 1/4 (still an even denominator)

    c) I think your method of generating a random number was perhaps biased - if you generate a random numerator and then a random denominator ...[text shortened]... use disproprtionately many of your generated numbers will simplify to simple fractions like 1/2.
    crap
  9. Joined
    26 Apr '03
    Moves
    26771
    01 Sep '03 16:141 edit
    Originally posted by TheMaster37
    crap
    I succumb to your devastating riposte. 🙄
  10. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    01 Sep '03 21:551 edit
    THe answer is 1/3. Good going iamatiger!

    Here's my proof. Let S(d) be the number of rationals in (0,N] with denominator d for some integer N.

    Clearly, we are counting pairs (m,d) such that gcd(m,d)=1. If d is prime, then:

    S(d) = N(1-1/d)

    If d has k distinct prime factors, then:

    S(d) = N(1-1/p1 - 1/p2 - ...-1/pk + 1/p1p2+...+1/p1p2p3p4p5...pk)

    = N(1-1/p1)(1-1/p2)...(1-1/pk)

    Thus if d is odd, then for all a, S(d*2^a) = S(d)/2.

    Thus for every even-denominator rational, there are two odd-denominator rationals. Thus the probability we want is 1/3.

    This illustrates the fact that being even guarantees the presence of a prime factor, 2, while being odd guarantees nothing.
  11. Standard memberFiathahel
    Artist in Drawing
    in your fridge
    Joined
    21 May '03
    Moves
    9766
    02 Sep '03 07:40
    Originally posted by royalchicken
    THe answer is 1/3. Good going iamatiger!

    Here's my proof. Let S(d) be the number of rationals in (0,N] with denominator d for some integer N.

    Clearly, we are counting pairs (m,d) such that gcd(m,d)=1. If d is prime, then:

    S(d) = N(1-1/d)

    If d has k distinct prime factors, then:

    S(d) = N(1-1/p1 - 1/p2 - ...-1/pk + 1/p1p2+...+1/p1p2p3p4 ...[text shortened]... t being even guarantees the presence of a prime factor, 2, while being odd guarantees nothing.
    There are some errors in your proof

    First of all you forgot a d in every line : for example S(d) = dN(1-1/d). This gives if S(d)=dN(1-1/p1)(1-1/p2)...(1-1/pk) then S(d*2^a)=(d*2^a)*N(1-1/2)(1-1/p1)(1-1/p2)...(1-1/pk)=S(d)*2^(a-1)

    So here you got a problem.
  12. DonationAcolyte
    Now With Added BA
    Loughborough
    Joined
    04 Jul '02
    Moves
    3790
    02 Sep '03 09:121 edit
    Originally posted by royalchicken
    Thus if d is odd, then for all a, S(d*2^a) = S(d)/2.
    Huh? Isn't it S(d)*2^(a-1) for all a>0?

    EDIT: Sorry, this follows from Fiathahel's point.
  13. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    02 Sep '03 12:484 edits
  14. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    02 Sep '03 12:513 edits
    Ok, I made a typo, but not exactly the one Fiathahel meant. If S(d) referred to the number of d-denominator rationals in (0,N] as I said, then indeed
    S(d) = dN(1-1/p1)....(1-1/pk) as Fiathehel said. However, I meant to say that S(d) counts rationals with NUMERATORS IN (0,N], ie those rationals in (0,N/d] so that the rest is as I said.

    S(d) = N(1-1/p1)(1-1/p2)....(1-1/pk) is p1,p2,...pk are the distinct prime factors of d.

    So for any prime r, S(dr^a) = (1-1/r)S(d), so S(d*2^a) = S(d)/2, which shows that the probability of choosing a random even-denom. rational is 1/3.

    In this situation, we can count the rationals with a maximum numerator regardless of changes in denominator. In the situation you mention based on my typo, we have the number of possible numerators, dN rather than N, growing as the denominator grows, which makes S(d) pretty meaningless since we can't make comparisons among different denominators.
  15. Standard memberroyalchicken
    CHAOS GHOST!!!
    Elsewhere
    Joined
    29 Nov '02
    Moves
    17317
    02 Sep '03 14:171 edit
    The proof from which I just exorcised a typo can also be stated more clearly by saying that S(d) = (N/d)*P(d), where P is the Euler totientfunction that counts the number of integers less than and prime to d. Since P is multiplicative, S(2d) = (N/2d)*P(2d) = (N/2d)*P(d)*P(2) = (N/d)*P(d)/2 = S(d)/2.
Back to Top

Cookies help us deliver our Services. By using our Services or clicking I agree, you agree to our use of cookies. Learn More.I Agree