# Number of random guesses needed to guess a number in a given set [duplicate]

I am not very good with probability theory and related stuff, so I would very much appreciate your help regarding a problem I have.

• Imagine arbitrarily picking an integer $n\in [1,N]$
• I want to guess $n$ by running a random number generator several times
• The random number generator spits out numbers $\in [1,N]$, with uniform distribution
• The random number generator does not keep track of previous guesses (i.e. can use the same guess more than once)

My question is: how can I estimate how many times do I have to run the random number generator, on average, before hitting the chosen number $n$?

I searched for an answer and found other posts, such as this one "Average number of guesses to guess number between 1 and 1000?", but there it was possible to get hints (higher/lower), so it's not really the same thing.

Thank you so much

EDIT: I wrote a python script to do some experiments and get some intuition. Looks like on average it takes $N$ guesses, but I am not sure whether this holds in general, and why this is the case.

Here is the script:

import random
import numpy

noTests = 100000
maxNumber = 100

noGuesses = []
targetNo = random.randint(0, maxNumber)

for i in range(1, noTests):

guessNo = 1

while True:
if random.randint(0, maxNumber) == targetNo:
break
guessNo = guessNo+1

noGuesses.append(guessNo)

avg = numpy.mean(noGuesses)

print "Average number of guesses to guess a number in [0,%d] is %d"%(maxNumber,avg)
print "Estimated over %d tests"%(noTests)

• The probability of not hitting the number every time you run the algorithm is $\frac{N-1}{N}$, thus the probability of not hitting it $n$ times in a row is $(\frac{N-1}{N})^n$. Hence the probability of hitting it in the first $n$ tries is $1-(\frac{N-1}{N})^n$. Now choose the allowed error and solve for $n$. – b00n heT Jun 5 '16 at 15:17
• Hint: Try finding the probability that the first $k$ guesses are wrong. – Steve Kass Jun 5 '16 at 15:17
• That is the classical Bernoulli Trial run, with success prob. $p=1/N$. re. en.wikipedia.org/wiki/Bernoulli_trial – G Cab Jun 5 '16 at 15:19

This is a classic problem in probability. The distribution for $N$ the first "hit" is called the geometric distribution. See the following related question: