Permutation probability

70 Views Asked by At

Let $S = \{1,2,3,4,5,...,n\}$.

Let $\Omega$ be set of permutation maps of $S$.

Let $\Phi : \mathbb{R} \to \mathbb{R}$ be strictly positive and strictly increasing map.

Consider positive function $P: \Omega \to \mathbb{R}$ defined by

$$P(\tau) = \prod_{j=1}^{n} \frac{\Phi(\tau(j))}{\sum_{k=j}^n \Phi(\tau(k))}.$$

I want to show that $P$ is probability function on $\Omega$. For that , I should show that $$\sum_{\tau \in \Omega} P(\tau)=1.$$

I tried to calculate
$$\sum_{l=1}^n\sum_{\tau(l)=1} P(\tau).$$

But it is difficult.

Is anyone want to help me?

1

There are 1 best solutions below

0
On BEST ANSWER

I do not need the monotonicity of $\Phi$, only positivity. And since we only need the values of $\Phi$ on $\Bbb N_1$, I will assume $\Phi:\Bbb{N}_1\to (0,\infty)$.

We prove this by induction on $n$. And since dealing with many values of $n$ at the same time, things can get confusing. So, I denote $S_n$ and $\Omega_n$ for $S$ and $\Omega$ corresponding to $n$. Since $P$ depends on both $n$ and $\Phi$, we write $P^{\Phi}_n$ for $P$ corresponding to a given pair $(n,\Phi)$.

The cases $n=1$ and $n=2$ are trivial. Suppose that $n\geq 3$ and we know the claim holds for $n-1$. For $k\in \{1,2,\ldots,n\}$, let $\Omega_n(k)$ denote the subset of $\Omega_n$ consisting of $\tau\in \Omega_n$ such that $\tau(1)=k$. Define $\Phi_{k}:\Bbb{N}_1\to(0,\infty)$ by $$\Phi_k(m)=\begin{cases}\Phi(m)&\text{if}\ m<k,\\ \Phi(m+1)&\text{if}\ m\geq k.\end{cases}$$ Define $s_k:\Bbb{N}_1\to\Bbb{N}_1$ to be $$s_k(m)=\begin{cases}m&\text{if }m\leq k,\\m-1&\text{if }m>k.\end{cases}$$ Let $\Gamma_{n,k}:\Omega_n(k)\to\Omega_{n-1}$ be the bijective map sending $$\tau=\begin{pmatrix}1&2&\cdots&n\\\tau(1)&\tau(2)&\cdots&\tau(n)\end{pmatrix}\mapsto \begin{pmatrix} 1 & 2 & \cdots &n-1\\ s_k\big(\tau(2)\big)&s_k\big(\tau(3)\big)&\cdots&s_k\big(\tau(n)\big)\end{pmatrix}=\Gamma_{n,k}\tau.$$ It follows that $$P^\Phi_n(\tau)=\frac{\Phi(k)}{\sum_{i=1}^n\Phi(i)}P^{\Phi_k}_{n-1}\left(\Gamma_{n,k}\tau\right)$$ for every $\tau\in\Omega_n(k)$. By induction, $$\sum_{\tau\in\Omega_n(k)}P^{\Phi_k}_{n-1}(\Gamma_{n,k}\tau)=\sum_{\sigma\in \Omega_{n-1}}P^{\Phi_k}_{n-1}(\sigma)=1.$$ That is, $$\sum_{\tau\in\Omega_n(k)}P_n^\Phi(\tau)=\frac{\Phi(k)}{\sum_{i=1}^n\Phi(i)}\sum_{\tau\in\Omega_n(k)}P^{\Phi_k}_{n-1}(\Gamma_{n,k}\tau)=\frac{\Phi(k)}{\sum_{i=1}^n\Phi(i)}.$$ Consequently, $$\sum_{\tau\in\Omega_n}P_n^\Phi(\tau)=\sum_{k=1}^n\sum_{\tau\in\Omega_k(n)}P_n^\Phi(\tau)=\sum_{k=1}^n\frac{\Phi(k)}{\sum_{i=1}^n\Phi(i)}=1.$$