1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Likelihood of pairs in a range?

  1. Jan 17, 2014 #1
    Running a computer script (included below) I was testing to see how long it would take to match two numbers when selected at random from within a range. To my surprise the percentage of possibilities explored before finding a correct answer decreased as i raised the range.

    Is this correct? It seems counter intuitive.

    Code (Text):


    import sys
    import random

    x = int(sys.argv[1])
    a = random.randint(0,x)
    b = random.randint(0,x)

    steps = 1
    combos = x**2

    while a != b:
        print('[{} {}]'.format(a,b), end=' ')
        a = random.randint(0,x)
        b = random.randint(0,x)
        steps += 1

    percent = (steps / combos) * 100

    print('[{} ! {}]'.format(a,b), end=' ')
    print('steps'.upper(), steps)
    print('possble combinations = {}'.format(combos))
    print('explored {}% possibilitys'.format(percent))
    Last edited by a moderator: Jan 17, 2014
  2. jcsd
  3. Jan 17, 2014 #2


    User Avatar
    Science Advisor

    Each pair selected has a 1/x probability of being a match. It does not matter what the first pair member is. The second pair member has 1/x probability of matching. The expected number of guesses to get a match is going to be around x.

    You are looking at the ratio of x to x2. Of course this decreases as x increases.
  4. Jan 17, 2014 #3
    I'm not familiar with python, but if you want to do some experimentation with random numbers, you probably want to make sure first of all that you are using something better than the default random number method available in the language. Perhaps consider the following and see if that changes the result:


    The pseudo-random generators of this module should not be used for security purposes. Use os.urandom() or SystemRandom if you require a cryptographically secure pseudo-random number generator.

    http://docs.python.org/2/library/random.html" [Broken]
    Last edited by a moderator: May 6, 2017
  5. Jan 17, 2014 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    It's 1/(x+1), not 1/x. The OP used randint(0,x), which returns a uniformly distributed random integer between 0 and x, inclusive.

    x+1, to be precise.

    Python's random module uses the Mersenne twister with a state size of 19937 bits. That is a very good pseudo random number generator. It is not the bad old rand().
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Similar Threads for Likelihood pairs range
B Domain and the codomain of a composite function