Let $X_1,X_2,X_3.\dots$ be iid Uniform $(0,1)$ and let $N_k$ be the minimum $n$ such that $$X_1^k+X_2^k+\cdots +X_n^k\le 1<X_1^k+X_2^k+\cdots +X_{n+1}^k, \quad k\in\mathbb{N}$$ How to find $\displaystyle \lim_{k\to\infty}\frac{E(N_k)}{k}$?


If $X_i$ is uniformly distributed over $(0,1)$, then $$ \mathbb{P}[X_i^k\leq t] = t^{\frac{1}{k}}$$ hence the pdf of $X_i^k$ is supported on $(0,1)$ and given by $\frac{1}{k}\,t^{\frac{1}{k}-1}$. Moreover, $$\begin{eqnarray*}\mathbb{P}[N_k\geq n]=\mathbb{P}[X_1^k+\ldots+X_n^k<1]&=&\int_{(0,1)^n}\mathbb{1}_{x_1^k+\ldots+x_n^k<1}\,d\mu\\&=&\frac{1}{k^n}\int_{(0,1)^n}\left(z_1\cdot\ldots\cdot z_n\right)^{\frac{1}{k}-1}\cdot\mathbb{1}_{z_1+\ldots+z_n<1}\,d\mu\\&=&\frac{\Gamma\left(\frac{1}{k}\right)^{n}}{k^n\cdot \Gamma\left(1+\frac{n}{k}\right)}\end{eqnarray*}$$ where the last step follows from the properties of the Dirichlet distribution.

It gives: $$\mathbb{E}[N_k]=\sum_{n\geq 1}\frac{\Gamma\left(1+\frac{1}{k}\right)^n}{\Gamma\left(1+\frac{n}{k}\right)}$$ but since the limit for $k\to +\infty$ of $\Gamma\left(1+\frac{1}{k}\right)^k$ equals $e^{-\gamma}$, by a Riemann sum argument:

$$ \lim_{k\to +\infty}\frac{\mathbb{E}[N_k]}{k}=\int_{0}^{+\infty}\frac{e^{-\gamma x}}{\Gamma(1+x)}\,dx = \color{red}{1.24941661444\ldots}.$$

  • $\begingroup$ You're quite right, my answer was too handwaving. However, numerical simulations seem to indicate a limit near $1.25$ -- if your result is correct, the convergence is extremely slow -- the numerical result is still above $1.25$ for $k=200$. $\endgroup$ – joriki Oct 17 '15 at 15:17
  • $\begingroup$ Why can you replace $\Gamma\left(1+\frac1k\right)^n$ by the limit of $\Gamma\left(1+\frac1k\right)^k$? $\endgroup$ – joriki Oct 17 '15 at 15:22
  • $\begingroup$ @joriki: there was an error, now the computation is fixed and the limit is close to $\frac{5}{4}$ as numerical computations suggest. I write $\Gamma\left(1+\frac{1}{k}\right)^n$ as $\left[\Gamma\left(1+\frac{1}{k}\right)^k\right]^{\frac{n}{k}}$, then exploit the dominated convergence theorem and a Riemann sum argument. $\endgroup$ – Jack D'Aurizio Oct 17 '15 at 15:30
  • 1
    $\begingroup$ I see -- very nice! $\endgroup$ – joriki Oct 17 '15 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.