Prove that this sequence of functions converges to a continuous function.

174 Views Asked by At

Let $F_{N}(\alpha)$ be the probability that a permutation of $N$ objects has greatest cycle length less than or equal to $N\alpha$, with $\alpha\in\mathbb{R}$. Prove that $$\lim_{N\to\infty}F_{N}(\alpha)$$ is continuous on $\mathbb{R}$.

I've tried to approach this using the $\epsilon-\delta$ definition of continuity but haven't had any luck so far. Obviously the limit is $1$ for $\alpha\geq1$ and $0$ for $\alpha\leq0$ so we only need to prove continuity on $[0,1]$. It seems somewhat intuitive but I'm having trouble formalising the argument.

1

There are 1 best solutions below

3
On

I will assume here that the limit function $F_N(\alpha)$ actually exists (which is not trivial...). If so, the function $F_N(\alpha)$ must be non-decreasing in $\alpha$. Our plan will be to bound the difference $$F_N(\alpha+\epsilon)-F_N(\alpha)$$ and show it goes to $0$ as $\epsilon$ does.

The difference $F_N(\alpha+\epsilon) - F_N(\alpha)$ is equal to the probability that the greatest cycle length is between $\alpha N$ and $(\alpha+\epsilon)N$, which is bounded above by the probability that any cycle is between those two lengths.

For a given $j$ between $1$ and $n$, let $X_j=1$ if $j$ is contained in a cycle of length in $[\alpha N, (\alpha+\epsilon)N)$. Let $X=X_1+\dots+X_N$ be the total number of such elements. We make a few observations:

  • For a given $j$, the length of the cycle containing $j$ is uniform between $1$ and $N$. This means that the probability of $X_j$ being $1$ is $\frac{\epsilon N}{N} = \epsilon$, so the expectation of $X_j$ is $\epsilon$.
  • By linearity of expectation, the expected value of $X$ is $N\epsilon$.
  • If $X$ is nonzero, then $X$ must be at least $\alpha N$.

Combining all the above, we have \begin{eqnarray*} F_N(\alpha+\epsilon) - F_N(\alpha) &\leq& P(X > 0) \\ &=& P(X \geq \alpha N) \\ &\leq& \frac{E(X)}{\alpha N} \, \, (\textrm{Markov's Inequality}) \\ &=& \frac{N \epsilon}{\alpha N} = \frac{\epsilon}{\alpha} \end{eqnarray*}

For any fixed $\alpha \in (0,1]$, this goes to $0$ as $\epsilon$ goes to $0$, so the function is continuous at $\alpha$. We still need to check continuity at $0$, i.e. that $F_N(\alpha)$ goes to $0$ as $\alpha \rightarrow 0$. But for this we can say

\begin{eqnarray*} F_N(\alpha) &\leq& P(\textrm{The cycle containing } 1 \textrm{ has length } \leq N \alpha) \\ &=& \frac{N \alpha}{N} = \alpha \end{eqnarray*}