Skip to main content

MA 415G course notes

Benjamin Braun

Section 4.5 Expected Values: Permutations

We next apply the tools we have developed to investigate expected values of random variables defined on permutations.
🔗

Checkpoint 4.5.1.

As our first example, let \(\inv\) be the random variable on \(\ss_n\) with the uniform distribution that counts the number of inversions in a permutation. Here is a plot (note the different scales on the axes!!!) where for each \(n\) from \(2\) to \(15\text{,}\) we randomly select \(1000\) permutations and compute the average value of \(\inv\) on those subsets. Do you have a guess for what \(E[\inv]\) might be? What is your reasoning?
🔗
Plot of experimental expected value of inv versus n.
Figure 4.5.2. Plot of experimental expected value of \(\inv\) versus \(n\text{.}\)
🔗
🔗

Example 4.5.3.

While it isn’t obvious from the plot, it turns out that
\begin{equation*} E[\inv] = \frac{n(n-1)}{4}\text{.} \end{equation*}
Here is a plot of our experimental values versus the graph of this function.
🔗
Plot of experimental expected value of inv versus n with the function x(x-1)/4.
Figure 4.5.4. Plot of experimental expected value of \(\inv\) versus \(n\) with the function \(y=x(x-1)/4\text{.}\)
🔗
🔗
Before we consider the case of inversions, let’s look at a simpler random variable on permutations. Let \(X\) be the random variable on \(\ss_n\) with the uniform distribution that counts the number of fixed points of a permutation. In other words, for \(\pi\in \ss_n\text{,}\) let
\begin{equation*} X(\pi)=|\{i\in [n] : \pi(i)=i\} |\text{.} \end{equation*}
🔗

Checkpoint 4.5.5.

Here is a plot where for each \(n\) from \(1\) to \(15\text{,}\) we randomly select \(1000\) permutations and compute the average value of \(X\) on those permutations. What do you think the expected value \(E[X]\) might be? What is your reasoning?
🔗
Plot of experimental expected value of number of fixed points versus n.
Figure 4.5.6. Plot of experimental expected value of number of fixed points versus \(n\text{.}\)
🔗
🔗

Proof.

Let \(X_i\) be the random variable defined by
\begin{equation*} X_i(\pi)=\begin{cases} 1 \amp \text{if } \pi(i)=i \\ 0 \amp \text{otherwise} \end{cases}\text{.} \end{equation*}
Using linearity of expectation, we have that
\begin{align*} E[X] \amp = E\left[\sum_{i=1}^n X_i\right] \\ \amp = \sum_{i=1}^n E[X_i] \\ \amp = \sum_{i=1}^n \sum_{\pi\in \ss_n} P(\pi)X_i(\pi) \\ \amp = \sum_{i=1}^n \sum_{\pi\in \ss_n: \pi(i)=i} \frac{1}{n!} \\ \amp = \sum_{i=1}^n \frac{(n-1)!}{n!} \\ \amp = \sum_{i=1}^n \frac{1}{n} \\ \amp = 1 \, . \end{align*}
🔗
🔗

Checkpoint 4.5.8.

  1. If we were to compute \(E[X_i]\) in the proof above using the probability that \(X_i=1\text{,}\) what would that probability be?
    🔗
    🔗
  2. How would you use it to compute \(E[X_i]\) by summing over \(0\) and \(1\text{?}\)
    🔗
    🔗
  3. How would this change/simplify the proof above?
    🔗
    🔗
🔗
🔗
Thus, on average, a permutation has exactly one fixed point, no matter how large \(n\) is.
🔗
Next, we consider the case of descents in a permutation.
🔗

Proof.

Let \(Y_i\) be the random variable defined by
\begin{equation*} Y_i(\pi)=\begin{cases}1 \amp \text{if } \pi(i)>\pi(i+1) \\ 0 \amp \text{otherwise} \end{cases} \, . \end{equation*}
Note that half of the permutations in \(\ss_n\) have a descent at position \(i\) (since for any ordering of the other \(n-2\) elements, there are two ways to order \(\pi(i)\) and \(\pi(i+1)\text{,}\) one with a descent and one without). Using linearity of expectation, we thus have that
\begin{align*} E[\des] \amp = E\left[\sum_{i=1}^{n-1} Y_i\right] \\ \amp = \sum_{i=1}^{n-1} E[Y_i] \\ \amp = \sum_{i=1}^{n-1} \sum_{\pi\in \ss_n} P(\pi)Y_i(\pi) \\ \amp = \sum_{i=1}^{n-1} \sum_{\pi\in \ss_n: \pi(i)>\pi(i+1)} \frac{1}{n!}\cdot 1 \\ \amp = \sum_{i=1}^{n-1} \frac{n! / 2}{n!} \\ \amp = \frac{n-1}{2} \, . \end{align*}
🔗
🔗

Checkpoint 4.5.10.

In the proof above is the observation that for each \(i\in [n-1]\text{,}\) exactly half of the permutations in \(\ss_n\) have a descent at position \(i\text{.}\) Does this observation help to simplify the calculation of \(E[Y_i]\) in the proof above using a probability interpretation of the indicator function?
🔗
🔗
We are now in a position to tackle the expected number of inversions.
🔗

Proof.

Let \(Z_{i,j}\) be the random variable defined by
\begin{equation*} Z_{i,j}(\pi)=\begin{cases}1 \amp \text{if } \pi(i)\gt \pi(j) \\ 0 \amp \text{otherwise} \end{cases} \, . \end{equation*}
Note that half of the permutations in \(\ss_n\) have an inversion at the positions \((i,j)\) (since for any ordering of the other \(n-2\) elements, there are two ways to order \(\pi(i)\) and \(\pi(j)\text{,}\) one with an inversion and one without). Using linearity of expectation, we thus have that
\begin{align*} E[\inv] \amp = E\left[\sum_{1\leq i\lt j\leq n} Z_{i,j}\right] \\ \amp = \sum_{1\leq i\lt j\leq n} E[Z_{i,j}] \\ \amp = \sum_{1\leq i\lt j\leq n} \sum_{\pi\in \ss_n} P(\pi)Z_{i,j}(\pi) \\ \amp = \sum_{1\leq i\lt j\leq n} \sum_{\pi\in \ss_n: \pi(i)\gt \pi(j)} \frac{1}{n!}\cdot 1 \\ \amp = \sum_{1\leq i\lt j\leq n} \frac{n! / 2}{n!} \\ \amp = \binom{n}{2}\frac{1}{2} \, .\\ \amp = \frac{n(n-1)}{4} \, . \end{align*}
🔗
🔗
Let’s consider next the expected number of cycles in a permutation.
🔗

Proof.

Let \(S=\{i_1,\ldots,i_k\}\subseteq [n]\) be a subset of size \(k\text{,}\) and let \(C_S\) be the random variable defined by
\begin{equation*} C_S(\pi)=\begin{cases}1 \amp \text{if } S\text{ is a cycle in } \pi \\ 0 \amp \text{otherwise} \end{cases} \, . \end{equation*}
Note that for a fixed ordering of the elements not in \(S\text{,}\) there are exactly \((k-1)! (n-k)!\) permutations in \(\ss_n\) where \(S\) forms a cycle, since there are \((k-1)! \) ways to arrange the elements of \(S\) into a cycle and \((n-k)! \) ways to arrange the other elements. Using linearity of expectation, we thus have that
\begin{align*} E[C] \amp = E\left[\sum_{S\subseteq [n]} C_S\right] \\ \amp = \sum_{S\subseteq [n]} E[C_S] \\ \amp = \sum_{S\subseteq [n]} \sum_{\pi\in \ss_n} P(\pi)C_S(\pi) \\ \amp = \sum_{S\subseteq [n]} \sum_{\pi\in \ss_n: S\text{ is a cycle in }\pi} \frac{1}{n!}\cdot 1 \\ \amp = \sum_{k=1}^n \sum_{\substack{S\subseteq [n] \\ |S|=k}} \frac{(k-1)! (n-k)!}{n!} \\ \amp = \sum_{k=1}^n \binom{n}{k} \frac{(k-1)! (n-k)!}{n!} \\ \amp = \sum_{k=1}^n \frac{1}{k} \\ \amp = H_n \, . \end{align*}
🔗
🔗
Note that in the proof above, a simplification could be made by recognizing that \(C_S\) is an indicator random variable for the event that \(S\) forms a cycle in the permutation, and the probability of this event is \(\frac{(k-1)!(n-k)!}{n!}\text{.}\)
🔗
🔗
PrevTopNext