Consider a random permutation $\sigma_{n}$ of $n$ distinct numbers from $1$ to $n$. Let $X_{n,k}$ denote the number of increasing subsequences of length $k$ over the random permutation $\sigma_{n}$. Find the expected value of $X_{n,k}$.
This problem is in the context of proving an upper bound on the expectation. This is discussed in the article here (Lemma 1.4, page 9). The argument and the answer is very trivial but I cannot wrap my head around that $$E(X_{n,k}) = {1 \over k!} {n \choose k}$$ This looks more like probability than expectation. Also, how does $X_{n,k}$ define over expectation? Is there a way to do the counting using some indicator variables?
Sure, we can use indicator functions here.
We are given a sequence $a_1, a_2, \dots, a_n$ which is a random permutation of $1,2,\dots,n$.
There are $\binom{n}{k}$ subsequences of this sequence of length $k$. For each such subsequence $s$, let $I_s$ be the random variable which is the indicator function of that subsequence being increasing, that is:
$$ I_s = \left\{ \begin{array}{ll} 0 & \mbox{if } s \text{ not increasing} \\ 1 & \mbox{if } s \text{ increasing} \end{array} \right. $$
Now, $X_{n,k} = \displaystyle\sum_{s} I_s$, so we have:
$$ E(X_{n,k}) = \displaystyle\sum_{s} E(I_s) $$
But the probability that a given subsequence $s$ of length $k$ is increasing is precisely $\frac{1}{k!}$, so for each $s$,
$$E(I_s) = \frac{1}{k!}$$
Thus we have:
$$E(X_{n,k}) = \displaystyle\sum_{s} E(I_s) = \frac{1}{k!} \binom{n}{k}$$