I am reposting a question on math.stackexchange which did not recieve good questions.
The orginal questio is at <https://math.stackexchange.com/questions/73091/distribution-of-a-maximum>.


Randomly select $n$ numbers from ${\{1,2,\dots,m\}}$ without replacement, and order the chosen elements increasingly: $X\_1 < X\_2 < \dots < X\_n$


And we can view each $X\_i$ as a random variable, and we can get $\mathbb{E}(X\_i) = \frac{(m+1)i}{n+1}$


And we can define $Y\_i=|X\_i-\mathbb{E}(X\_i)|$ which is the distance of each variable to its corresponding expectation. 


And we can also define $Z = \max\_{1 \le i \le n} Y\_i$


So what is the distribution of $Z$? And any bound of $Z$ is helpful.



Distribution of a maximum
If, as suggested by Ori Gurel-Gurevich, we sample from uniform distribution on $[0,1]$, then $Z$ will typically be of order $1/\sqrt{n}$. 


A convenient way of generating the points $X\_1,\dots,X\_n$ in order is letting $W\_1,\dots,W\_{n+1}$ be independent exponential(1) variables with partial sums $S\_k = W\_1+\cdots+W\_k$, and finally letting $X\_k = S\_k / S\_{n+1}$.
We have $$ \left|X\_k - \frac{k}{n+1}\right| = \left|\frac{S\_k}{S\_{n+1}} - \frac{k}{n+1}\right| \leq 
\left|\frac{S\_k}{n+1} - \frac{k}{n+1}\right| + \left|\frac{S\_k}{n+1} - \frac{S\_k}{S\_{n+1}}\right| $$
$$ \leq \frac{\left|S\_k-k\right|}{n+1} + \frac{S\_{n+1}}{S\_k}\cdot \left| \frac{S\_k}{n+1} - \frac{S\_k}{S\_{n+1}}\right| = \frac{\left|S\_k-k\right| + \left|S\_{n+1} - (n+1)\right|}{n+1},$$
and in particular 
$$\max\_{k\leq n} \left|X\_k - \mathbb{E}X\_k\right| \leq \frac2{n+1}\cdot\max\_{k\leq n+1} \left|S\_k - k\right|.$$
It is relatively easy to see that $\mathbb{E}\max\_{k\leq n} \left|S\_k-k\right| = O(\sqrt{n})$ and consequently that $\mathbb{E} \max\_{k\leq n} \left|X\_k - \mathbb{E}X\_k\right| = O(n^{-1/2})$. This is because $S\_n-S\_k$ is independent of $S\_k$. Therefore if $S\_k$ deviates wildly from its mean, then with decent probability (namely when $S\_n-S\_k$ deviates ever so slightly in the same direction), $S\_n$ will deviate just as wildly from its mean. More precisely, $$Pr\left(\left|S\_n - n\right| > t\right) \geq C\cdot Pr\left(\left|S\_k-k\right| > t \ \text{for some $k\leq n$}\right),$$
where $C$ is simply a positive lower bound on the probability that a sum of independent exponentials deviates from its mean in a given direction. Consequently \begin{equation} \mathbb{E} \max\_{k\leq n} \left|S\_k-k\right| = \int\_0^\infty Pr\left(\max\_{k\leq n}\left|S\_k-k\right| > t\right) \, dt \end{equation} \begin{equation} \leq \frac1C \int\_0^\infty Pr\left(\left|S\_n-n\right| > t\right)\, dt = \frac1C\cdot \mathbb{E}\left|S\_n-n\right| = O(\sqrt{n}). \end{equation}


EDIT:
To return to the original problem, we choose $n$ numbers independently and uniformly in the interval $[0,m-n+1]$ and let $$U\_1\leq U\_2 \leq \cdots \leq U\_n$$ be the sorted sequence. Now let $$X\_i = \left\lfloor U\_i+i\right\rfloor.$$ The sequence $X\_1,\dots,X\_n$ is now generated according to the question (and therefore not the same as the $X\_i$'s earlier in this post). 


Scaling up the result above by a factor $m-n+1$, we see that the maximum deviation of a $U\_i$ from its mean is of order $$O\left(\frac{m}{\sqrt{n}}\right),$$ while the difference between $X\_i$ and $U\_i$ is of order $n$. Therefore the maximum deviation of $X\_i$ from its mean is of order $$O\left(\frac{m}{\sqrt{n}}+n\right),$$
where the first term will dominate when $m>>n^{3/2}$. On the other hand if $m$ is smaller, say of the same order as $n$, it must clearly be possible to achieve sharper bounds.


