Distribution induced by PMF $k \mapsto \binom{n}{k} \binom{n - k}{r - 2k} 2^{r - 2k} \binom{2n}{r}^{-1}$

129 Views Asked by At

When selecting $r$ shoes from $n$ pairs of shoes, the probability that there are exactly $k$ matching pairs amongst the $r$ selected shoes is given by $$ \mathfrak{p}_{n}^{(r)}: \left\{0, \ldots, \left\lfloor\frac{r}{2}\right\rfloor\right\} \to [0,1], \ k \mapsto \binom{n}{k} \binom{n - k}{r - 2k} 2^{r - 2k} \binom{2n}{n}^{-1}, $$ where $r \le n$ and $r, n \in \mathbb{N}$, as detailed i.e. here.

Upon stumbling about this post I wondered if $\mathfrak{p}$ is a PMF and what its expected value, etc. are and if it can be characterised by any off the "standard" probability distributions.

Concretely, I want to

  1. Verify $ \sum_{k = 0}^{\left\lfloor\frac{r}{2}\right\rfloor} \mathfrak{p}_{n}^{(r)} = 1, $ which is equivalent to $$ \sum_{k = 0}^{\left\lfloor\frac{r}{2}\right\rfloor}\binom{n}{k} \binom{n - k}{r - 2k} 2^{r - 2k} = \binom{2n}{r}. $$

  2. Find $$ \mathbb{E}[X] = \sum_{k = 0}^{\left\lfloor\frac{r}{2}\right\rfloor} \frac{k \cdot \binom{n}{k} \binom{n - k}{r - 2k} 2^{r - 2k}}{\binom{2n}{r}}, $$ where $X \sim P$ and $P$ is the distribution induced by the PMF $\mathfrak{p}_{n}^{(r)}$.

Unfortunately, the above mentioned post didn't really help me since I want to to solve / calculate those in an elementary fashion, without generating functions or integrals (I am aware an able to use the probabilty generating function, though).

1

There are 1 best solutions below

2
On

I'm not sure what your goal is with (1); $\mathfrak{p}_n^{(r)}$ is a PMF by construction, assuming your formula is right. If you want to be more explicit/rigorous about this, that can be done by defining some random variables.

Let $S = [n] \times \{1, 2\}$ be the set of all shoes, and let $T$ be a random subset of $S$ of size $r$, so $T$ is chosen uniformly from all $\binom{2n}{r}$ subsets of $S$ of size $r$. Now let $P \subset [n]$ be the set of pairs of shoes in $T$, so $P = \{i \in [n] : (i, 1), (i, 2) \in T\}$. Then $\mathfrak{p}_n^{(r)}$ is just the PMF of the random variable $|P|$.

To prove this, note that $\mathbb{P}[|P| = k]$ is the fraction of sets $T$ which have $k$ pairs and $r - 2k$ unpaired shoes. Such a $T$ is determined uniquely by the corresponding set $P$ of pairs, the set $U \subset [n]$ of unpaired shoe types, and the parities of all the unpaired shoes (i.e. whether they are left or right). There are $\binom{n}{k}$ ways to choose $P$, $\binom{n-k}{r-2k}$ ways to choose $U$ given $P$, and $2^{r-2k}$ ways to choose parities of the unpaired shoes, hence $\binom{n}{k}\binom{n-k}{r-2k} 2^{r-2k}$ such $T$, out of a total of $\binom{2n}{r}$ possible $T$, giving $$\mathbb{P}[|P| = k] = \binom{n}{k}\binom{n-k}{r-2k} 2^{r-2k} \binom{2n}{r}^{-1} = \mathfrak{p}_n^{(r)}$$ as desired. It immediately follows that $$1 = \sum_{k=1}^\infty \mathbb{P}[|P| = k] = \sum_{k=1}^{\lfloor r/2 \rfloor} \binom{n}{k}\binom{n-k}{r-2k} 2^{r-2k} \binom{2n}{r}^{-1}$$ hence $$\sum_{k=1}^{\lfloor r/2 \rfloor} \binom{n}{k}\binom{n-k}{r-2k} 2^{r-2k} = \binom{2n}{r}$$

To answer (2), for each $i$ let $A_i$ be the event that the $i$-th pair of shoes is in $T$, i.e. that $(i, 1), (i, 2) \in T$, so letting $\mathbf{1}_{A_i}$ be the indicator variable of $A_i$, we have $|P| = \sum_{i=1}^n \mathbf{1}_{A_i}$, hence by linearity of expectation, $$\mathbb{E}[|P|] = \sum_{i=1}^n \mathbb{E}[\mathbf{1}_{A_i}] = \sum_{i=1}^n \mathbb{P}[A_i].$$ But the number of $T$ containing $(i, 1), (i, 2)$ is just $\binom{2n-2}{r-2}$, hence for each $i$ we have $$\mathbb{P}[A_i] = \frac{\binom{2n-2}{r-2}}{\binom{2n}{r}} = \frac{r(r-1)}{2n(2n-1)}$$ which gives $$\mathbb{E}[|P|] = n \cdot \frac{r(r-1)}{2n(2n-1)} = \frac{r(r-1)}{4n-2}.$$ Note that this last formula is just $\frac{1}{2n-1} \binom{r}{2}$, which suggests another (arguably easier) approach we could have taken to compute $\mathbb{E}[|P|]$.