probability event linked with uniform order statistics

Question

Given$$U_1,\ldots,U_N\stackrel{\text{iid}}{\sim}\mathcal U(0,N)\quad N\in\mathbb N^*$$ consider the event $$\bigcap_{i=1}^N\{U_{(i)}\le i\}$$ where $$U_{(1)}<U_{(2)}<\cdots<U_{(N)}$$ denote the order statistics. This event has, I believe, the probability $$\frac{N!}{N^N}\,\int_0^1\int_{u_1}^2\cdots\int_{u_{N-1}}^N\,\text du_N\cdots\text du_1$$ Is there any chance this integral has a simple expression for all $N$'s? Computation is easy for $N=2,3,4$ but I do not see a pattern.

Answer 1

The probability is $$ (N+1)^{N-1} \over N^N $$ This process is equivalent to the parking function problem. In that problem, there are $N$ cars trying to park in a parking lot with $N$ spaces. The spaces are numbered $1$ to $N$. Each car independently chooses a preferred space number uniformly between $1$ and $N$. The cars then try to park one at a time. If a car prefers space number $a$, then they will successfully park if an only if one of the spaces in the range $\{1,\dots,a\}$ is available. The parking function problem asks, in this setup, what is the probability that all cars will successfully park?

In order for all cars to succeed, there needs to be at most one car which prefers space $1$, at most $2$ cars which prefer spaces $1$ or $2$, and in general, for each $i\in\{1,\dots,N\}$, there needs to be at most $i$ cars which prefer spaces in $\{1,\dots,i\}$. This is exactly equivalent to the condition $\{U_{(i)}\le i\}$ for your problem.

For a combinatorial proof that exactly $(N+1)^{N-1}$ of the $N^N$ preferences vectors are successful, see my other MSE answer, which quotes a solution by Richard Stanley.