likelihood of pairs in a range?


by derrend
Tags: likelihood, pairs, probability, random, range
derrend
derrend is offline
#1
Jan17-14, 06:37 AM
P: 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--:
#!/usr/bin/python3

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()
print()

print('[{} ! {}]'.format(a,b), end=' ')
print('equality!'.upper())
print('steps'.upper(), steps)
print('possble combinations = {}'.format(combos))
print('explored {}% possibilitys'.format(percent))
Phys.Org News Partner Mathematics news on Phys.org
Researchers help Boston Marathon organizers plan for 2014 race
'Math detective' analyzes odds for suspicious lottery wins
Pseudo-mathematics and financial charlatanism
jbriggs444
jbriggs444 is offline
#2
Jan17-14, 09:53 AM
P: 748
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.
hddd123456789
hddd123456789 is offline
#3
Jan17-14, 10:15 AM
P: 76
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:

"Warning

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"

D H
D H is online now
#4
Jan17-14, 10:54 AM
Mentor
P: 14,456

likelihood of pairs in a range?


Quote Quote by jbriggs444 View Post
Each pair selected has a 1/x probability of being a match.
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.

The expected number of guesses to get a match is going to be around x.
x+1, to be precise.


Quote Quote by hddd123456789 View Post
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.
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().


Register to reply

Related Discussions
Suppose A and B are n n matrices. Show that range(AB) ⊆ range(A) Calculus & Beyond Homework 4
Suppose A and B are n n matrices. Show that range(AB) ⊆ range(A) Calculus & Beyond Homework 5
Physics projectile problem - finding vertical range using the horizontal range Introductory Physics Homework 1
Photon Pairs - Can photons travel in pairs? Quantum Physics 7
pairs of primes separated by a single number are called prime pairs Brain Teasers 12