2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – owen88 Dec 19 '17 at 17:47
  • $\begingroup$ 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). $\endgroup$ – Sindbag Dec 19 '17 at 17:55
  • $\begingroup$ 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. $\endgroup$ – owen88 Dec 19 '17 at 18:44
0
$\begingroup$

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*}

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.