Assume $n$ random permutations $\pi_1,\pi_2,\ldots,\pi_n: \lbrace 1,2,\ldots,m \rbrace \rightarrow \lbrace 1,2,\ldots,m \rbrace$. Let $X_i = \min(\pi_1(i),\pi_2(i),\ldots,\pi_n(i))$ and $Y = \max(X_1, X_2, \ldots, X_m)$. What is the expectation of $Y$, $E(Y)$, as function of $n$? An upper bound approximation for $E(Y)$ would also be very helpful.
Obviously, we have $E(Y)=m$ for $n=1$ and $E(Y)=1$ for $n\rightarrow\infty$.
I know that the distribution of $X_i$ is given by $P(X_i\leq k) = 1 - \left(1-\frac{k}{m}\right)^n$. However, since $X_1,X_2,\ldots,X_m$ are not independent, it is not possible to get the distribution of $Y$ by $P(Y \leq k) = P(X_1 \leq k \wedge X_2 \leq k \wedge \ldots \wedge X_m\leq k) \neq P(X_1 \leq k) \cdot P(X_2 \leq k) \cdot\ldots \cdot P(X_m \leq k)$.
