Randomly Choosing a N-Bit Prime I've been studying some number theory, and I came across this problem:


  Lagrange’s prime number theorem states that as N increases, the number of primes less than $N$ is $Θ(N/ log(N))$. 
  
  Consider the following algorithm to choose a random n-bit prime:
  
  1) Pick a random n-bit number $k$.
  
  2) Run a primality test on $k.$
  
  3) If it passes the test, output $k$; else repeat the process.
  
  Show that this algorithm will sample on average $O(n)$ random numbers before hitting a prime.


I'm guessing I need to approach this probabilistically. Let $p$ be the probability that we randomly choose a prime. Let $E$ be the expected number of random numbers to choose before hitting a prime. Then, I need to express $E$ in terms of $p$, and show that it is less than or equal to $n$, right? Since, if we sample on average $O(n)$ numbers, then the expectation $E$ should be $\le n$.

But I'm a bit stuck on how to go about doing this. Is each event of choosing a random number binomial? Either we choose a prime or we don't, and each event is independent. But the expectation of a binomial RV is $np$, which is clearly not $\le n$.

I feel like I'm going about this all wrong. What am I missing here? Am I even on the right track? Thanks for your help.
Actually you should be thinking about a geometric random variable, not a binomial RV, since you're interested in the number of times that you have to sample before you hit a prime. And each sampling event is actually a Bernoulli trial (with probability of choosing a prime $p = \Theta(1/\log {2^n}$), where $n$ is the number of bits).

And for showing that the expected value is $O(n)$, you don't need to show that it's less than $n$. You actually need to show that there are some constants $k$ and $N$ such that the expected value is less than $kn$ for all $n \ge N$.

But besides that, you're on the right track.