# Expected value of position in subset.

I have set of $n$ elements $[0, ... n-1]$.

I randomly pick a subset $S$ of $k$ elements (also ordered).

Assume I have $t \in \{1, .. k\}$. What is expected value of $t$-th position in ordered subset?

I try to solve it like this:

$E\big[S_{t}\big] = \sum_{i=1}^{n} \big((i - 1) * P(S_{t}=(i-1))\big)$

$P(S_{t} = i) = \cfrac{\binom{i - 1}{t-1} * \binom{n-i}{k-t}}{\binom{n}{k}} .$

Here:

$\binom{i - 1}{t-1}$ is for selecting prefix;

$\binom{n-i}{k-t}$ is for postfix;

But I can't simplify this equality much further (I guess that sum of product of combinations could be simplified).

• I think you will find it easier if you start indexing from $1$; i.e. considering the set $\{1,\ldots, n\}$, and also assuming $t \in \{1,\ldots, k\}$: this will facilitate working with Binomials. Can you also explain why you think you need the factor $\frac1n$ in the probability. Have you tried some explicit examples? Eg. n = 5, k = 3, and t = 2? – owen88 Dec 19 '17 at 17:47
• It was my last thought about $\frac{1}{n}$, may be it's not valid (thought it's like select an element $i$ and then select prefix and postfix). – Sindbag Dec 19 '17 at 17:55
• You do not need the `select an element i' part, as this is assumed in the statement $P[S_t = i]$; i.e. you are counting those events for which the $t$-th element is $i$; otherwise your logic is correct. It'll help if you check some small examples as I prompted above. – owen88 Dec 19 '17 at 18:44

As in my comment above, I will consider the set to be $\{1,\ldots, n\}$, and let $t \in \{1,\ldots, k\}$ denote the position of interest, i.e. $S_t$ is the value of the $t$-th element of the random subset $S$, when in increasing order.

In this case, we can show that

$$P(S_t = i) = \frac{\binom{i-1}{t-1} \binom{n-i}{k-t} }{\binom{n}{k} }$$

Now substituting this into the formula for expectation:

\begin{align*} E[S_t] & = \sum_{i=1}^n i \frac{\binom{i-1}{t-1} \binom{n-i}{k-t} }{\binom{n}{k} } \\ & = \frac{1}{\binom{n}{k} } \sum_{i = 1}^n i \binom{i-1}{t-1} \binom{n-i}{k-t} \end{align*}

Using the formula: $$i \binom{i-1}{t-1} = t \binom{i}{t}$$

then the summation can be written as:

\begin{align*} \sum_{i=1}^n i \binom{i-1}{t-1}\binom{n-i}{k-t} &= t \sum_{i=1}^n \binom{i}{t}\binom{n-i}{k-t} \\ & = t \left( \sum_{i=0}^n \binom{i}{t}\binom{n-i}{k-t} - \binom{0}{t}\binom{n}{k-t} \right) \end{align*} where we have extended the sum over the range $i = 0,\ldots, n$ (instead of $i = 1, \ldots, n$). The first of the two terms is identified as the Vandermonde identity, whilst the second simplifies to $0$ so that

\begin{align*} \sum_{i=1}^n i \binom{i-1}{t-1}\binom{n-i}{k-t} &= t \binom{n+1}{k+1} \end{align*}

So over all, we have:

\begin{align*} E[S_t] &= t \frac{ \binom{n+1}{k+1} }{\binom{n}{k}} \\ & = t \frac{n+1}{k+1} \end{align*}

• Are you sure about Vandermonde's identity? We have $i$ changing, whereas Vandermonde's requires $t$ to be changing. – Sindbag Dec 19 '17 at 18:56
• See equation (9), en.wikipedia.org/wiki/… If you agree with my answer, will you please like and accept it. Thanks – owen88 Dec 19 '17 at 19:07
• Great, thanks a lot! Can't like it - too little rating :( – Sindbag Dec 19 '17 at 19:17
• No problem! Glad to have helped. – owen88 Dec 19 '17 at 19:18