Pick $k$ uniform independent random integers $x_1,\dots,x_k\in\{0,1,\dots,2^t-2,2^t-1\}$ and denote $y_{\sigma(i)}=x_i$ where $\sigma$ is a permutation in $S_n$ such that $y_1\leq y_2\leq\dots\leq y_{k-1}\leq y_k$ holds.

Define the gaps $g_1,\dots,g_{k-1}$ by $g_i=y_{i+1}-y_i$.

  1. What is the probability distribution $P(\sum_{i=1}^{k-1}g_i^2)$?

  2. What is the distribution that $g_{max}-g_{min}<r$ holds at an $r\geq0$?


Your Answer

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

Browse other questions tagged or ask your own question.