Given a function consisting of two steps
    Step 1 : Pick a random number in the range [1,...,n]
    Step 2 : If that number == X,skip 
             else goto step 1

What is the expected number of times Step 1 will run before exiting ?(Assuming that X is in the range [1....n]


2 Answers 2


I'm guessing X is some value in $\{1,\dots,n\}$, otherwise the expected value is infinite!

Anyways, what you are asking for is the expected value of a geometric random variable, with density $(1-\frac1{n})^{k-1}\frac1{n}$, where $k$ is the number of times you need to draw a random number from $\{1,\dots,n\}$. You can try to compute the expected value by hand yourself, but it is well understood that the expected value is $\frac1{\frac1{n}}=n.$


Assuming that $X$ lies in the range $[1,\ldots,n]$, you have probability $1/n$ of hitting it, so this is a series of Bernoulli trials with $p=1/n$, and the expected number of trials up to and including the first success is $1/p=n$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .