The original exercise that I'm trying to solve was Stochastic process over the expected time of tasting all $N$ dishes of a restaurant this one, with the addition of "show that the expected value of visits (let that be X) is

$$ \mathbb{E}[X] \sim N\log(N)$$

for $N\rightarrow \infty$.

I have shown that $$\mathbb{E}[X]=N\sum_{i=1}^{N} \frac{1}{i}$$ but I'm having a hard time with the second half of the exercise.

I said that for any k we know that:

$$ \sum_{i=1}^{k} \frac{1}{i} > \int_{1}^{k+1} \frac{1}{x} dx = \ln(k+1)$$

because it is the harmonic series. So, for $N\rightarrow \infty$ that would be:

$$X = N\sum_{i=1}^{N} > N\ln(N+1) \sim N\ln(N)$$

for $N\rightarrow \infty$.

But the exercise asks for log(N) not ln(N) and I am not sure if my approach is correct... How do I prove this?

  • 1
    $\begingroup$ Other than for very particular subfields (e.g. sometimes in information theory), $\log$ usually denotes the base $e$ logarithm in probability. I.e. $\log=\ln$. $\endgroup$
    – Oxonon
    Commented Dec 5, 2021 at 17:35
  • $\begingroup$ You might be interested in $H_{n}$ , the nth Harmonic Number. and that $\frac{H_{n}}{\ln(n)}\to 1$ . $\endgroup$ Commented Dec 5, 2021 at 18:18
  • 1
    $\begingroup$ Even if $\log$ means $\log_{10}$ here, it won’t affect the order. $\endgroup$
    – Q9y5
    Commented Dec 6, 2021 at 12:11


You must log in to answer this question.

Browse other questions tagged .