NBHM 2020 PART A Question 7 Solution

From the collection of all permutation matrices of size $10×10$, one such matrix is randomly picked. What is the expected value of its trace?  (A permutation matrix is one that has precisely one non-zero entry in each column and in each row, that non-zero entry being 1).
Solution:
Direct method: Expectation is nothing but the average. We will calculate the avarage. Let $P_n$ be the set of all $n \times n$ permutation matrices, then there are $n!$ many permuation matrices one for each permuation in $S_n$ (see below for the precise definition). We get the average (expected) trace as, 
$$\begin{align*}\frac{1}{10!}\sum_{A\in P_{10}}\text{tr}(A) &= \frac{1}{10!}\sum_{A\in P_{10}}\sum_{i=1}^{10}A_{ii} \\&= \frac{1}{10!}\sum_{i=1}^{10}\sum_{A\in P_{10}}A_{ii} \\&= \frac{1}{10!}\sum_{i=1}^{10}9! \\&= \frac{10\cdot9!}{10!} \\&= 1\end{align*}$$
Probabilistic method
Let $\sigma$ be a permutation in $S_n$ and $A_{\sigma}$ be the associated permutation matrix. For example, consider the permutation $\sigma = (1)(234)(5)$ in $S_5$, then the associated permutation matrix is obtained by permuting the rows (or colums (fix a convention)) of the $5 \times 5$ identity matrix. Hence $$A_{\sigma} = \begin{bmatrix} 1&0&0&0&0\\0&0&0&1&0\\ 0&1&0&0&0\\0&0&1&0&0\\0&0&0&0&1\\\end{bmatrix}.$$ Note that the second row of the identity matrix moved to third row, third row moved to fourth row and fourth row moved to second row as in the permutation $\sigma$. Other rows are not disturbed bacause they are not permuted by the permutation $\sigma$.
Observation: $\text{Trace } A_{\sigma} = \text{the number of fixed points of } \sigma$.
Proof:  $i$ th row contribute to trace iff $i$ th row is not disturbed iff $\sigma(i)=i$.
So we can rephrase the given question as, from the set of all $10 \times 10$ permutations $S_{10}$ one permutation is randomly picked. What is the expected value of its number of fixed points?  
Consider $1 \le i \le 10$, then the set $\{\sigma \in S_{10} : \sigma(i) = i\}$ has $9!$ number of elements. We get that the probability $p_i$ of $i$ being fixed is $\frac{9!}{10!} = \frac{1}{10}$. This probability is same for any $1 \le i \le 10$. Now, the required expected number of fixed points is equal to $\sum_{i=1}^{10} p_i = \sum_{i=1}^{10} \frac{1}{10} = 1$ (By the linearity of the expectation).
Share to your groups:
FOLLOW BY EMAIL TO GET NOTIFICATION OF NEW PROBLEMS. SHARE YOUR DOUBTS AND COMMENTS BELOW IN THE COMMENTS SECTION. ALSO, SUGGEST PROBLEMS TO SOLVE.

No comments:

Post a Comment

Featured Post

NBHM 2020 PART A Question 4 Solution $$\int_{-\infty}^{\infty}(1+2x^4)e^{-x^2} dx$$

Evaluate : $$\int_{-\infty}^{\infty}(1+2x^4)e^{-x^2} dx$$ Solution : $$\int_{-\infty}^{\infty}(1+2x^4)e^{-x^2} dx = \int_{-\infty}^{\inft...

Popular Posts