# Prove that the expected number of visits is $X\sim N \log N$ for $N\rightarrow \infty$.

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?

• 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$. Commented Dec 5, 2021 at 17:35
• You might be interested in $H_{n}$ , the nth Harmonic Number. and that $\frac{H_{n}}{\ln(n)}\to 1$ . Commented Dec 5, 2021 at 18:18
• Even if $\log$ means $\log_{10}$ here, it won’t affect the order.
– Q9y5
Commented Dec 6, 2021 at 12:11