Understanding proof about uniform permutations

Question

I'm having trouble understanding this proof I came across. In particular, I don't understand how the function is a bijection (or what exactly it is a map between). I also don't see why we must have that $\sum_i a_i =1 \implies P[\sigma(v) = \min_{u\in A} \sigma(u)] = 1/|A|$. I would really appreciate some insight here!

Lemma. Let $\sigma$ be a uniformly random permutation on $[n]:=\{1,\cdots,n\}$, let $A\subseteq [n]$. Then, for any $v\in A$, $$P[\sigma(v) = \min_{u\in A} \sigma(u)]=\frac{1}{|A|}.$$

Proof. The statement is trivial if $|A|=1$.

For $|A|>1$, let $v\neq v'$ with $v,v'\in A$. Then the function $f$ on the set of permutations which exchanges $\sigma(v)$ and $\sigma(v')$ is a bijection. Therefore $q_v=q_{v'}$ where $q_v= P[\sigma(v) = \min_{u\in A} \sigma(u)]$. Since $\sum_{v\in A} q_v=1$, we derive that $q_v=\frac{1}{|A|}.$

Answer 1

This proof is a formal way of saying "By symmetry, every $v \in A$ has an equal chance of having the smallest image under $\sigma$; since there are $|A|$ elements in $A$, each of them has a $\frac1{|A|}$ chance."

Intuitively, it is clear that $\sigma$ isn't any more likely to map any one element of $A$ to smaller values than another element. To make this rigorous, we pick two arbitrary values $v, v' \in A$, and argue that $q_v = \Pr[\sigma(v) = \min_{u \in A} \sigma(u)]$ is equal to $q_{v'} = \Pr[\sigma(v') = \min_{u \in A} \sigma(u)]$. We do this by finding a bijection between

1. Permutations $\sigma$ such that $\sigma(v) = \min_{u \in A} \sigma(u)$, and
2. Permutations $\sigma$ such that $\sigma(v') = \min_{u \in A} \sigma(u)$.

If there is such a bijection, then we conclude there's an equal number of permutations of both types. From there, because all permutations are equally likely, we conclude that $q_v = q_{v'}$: the probability of picking a permutation of the first type is the same as the probability of picking a permutation of the second type.

The map $f$ which takes a permutation $\sigma$ and swaps $\sigma(v)$ with $\sigma(v')$ is a bijection because:

• It maps permutations of the first kind to permutations of the second kind.
• It has an inverse $f^{-1}$ which maps permutations of the second kind to permutations of the first kind. In fact, $f^{-1}$ is $f$ itself.

Once we know that $q_v = q_v'$ for any $v, v' \in A$, we know that $$ 1 = \sum_{u \in A} q_u = \sum_{u \in A} q_v = |A|q_v $$ and therefore $q_v = \frac1{|A|}$.