Expected value of maximum consecutive distance in a uniformly random permutation How does one compute $\mathbb{E}[\max_{1\le i < n} |\sigma(i) - \sigma(i+1)|]$ where the expectation is taken over a uniformly random permutation $\sigma \in \mathbb{P}_n$, the set of all permutations on $[n]$?
Is there a recursion for $c^n_t$ that counts the number of permutations $\sigma$ on $[n]$ such that $\max_{1\le i < n} |\sigma(i) - \sigma(i+1)| \le t$?
 A: A naive approximation for the second question. The restriction of having a permutation of length $n$ with consecutive distances not greater than $t$ prohibits a total number of pairs given by $ 2 \times (1 + 2 + \cdots n - t-1) = (n-t)(n-t-1)$
The total number of a priori pairs is $n(n-1)$. The probability that a given pair violates the restriction is then 
$$\frac{(n-t)(n-t-1)}{n (n-1)}$$
If we assume (very rough approximation!) that the probability that all the pairs violate/fit the restriction are independent, the we have a probability of "success" given by
$$p_{n,t}=\left(1-\frac{(n-t-1)(n-t)}{n (n-1)}\right)^{n-1} = 
\left( \frac{t \, (2 n - t -1)}{n \, (n-1)} \right)^{n-1}$$
If we further assume that $n \gg 1$:
$$p_{n,t} \approx \left(\frac{2 t }{n}\right)^{n-1} e^{-(t-1)/2} $$
The number of allowed permutations then can be approximated as
$$c_{n,t} = n! \; p_{n,t}  \approx \left(\frac{2 t }{e}\right)^{n-1} e^{-(t-1)/2} \sqrt{2 \pi \, n}$$
I've made a few simulations and the approximation does  not seem too bad.
