Expected number of consecutive numbers from a uniform draw

Question

Say we pick $k$ numbers uniformly from $n$ without replacement and no order.

What is the expected number of consecutive numbers we will get?

For example, for $n=4, k=2$, only a draw of $(1,2),(2,3),(3,4)$ will result in $1$ consecutive numbers, so the expected number is $0.5$

I can also use a good upper bound instead of the expected value.

Answer 1

Assume $2 \leq k \leq n$. Let $S$ be a $k$-element subset of $[n]:=\{1, \dots, n\}$ chosen uniformly at random among all $k$-element subsets of $[n]$. For $i,j \in [n], i\neq j,$ define $$ X_{i,j} = \begin{cases} 1, i\in S \text{ and } j \in S \\ 0, \text{ otherwise. } \end{cases} $$ Then the number of consecutive pairs of numbers in $S$ is $$ X:= \sum_{i = 1}^{n-1} X_{i,i+1}. $$ Note that $$ \mathbb{E}[X_{i,j}] = P[i\in S \land j\in S] = \frac{\binom{n-2}{k-2}}{\binom{n}{k}}. $$ Thus by linearity of expectation we have: $$ \mathbb{E}[X] = \sum_{i = 1}^{n-1}\mathbb{E}[X_{i,i+1}] = (n-1)\frac{\binom{n-2}{k-2}}{\binom{n}{k}}. $$

Answer 2

Let $X_i$ be the indicator of the event that $i$ and $i+1$ are chosen. Then $$\mathbb{E}[X_i]=\frac{{n-2 \choose k-2}}{{n \choose k}}.$$

Then,

$$ \sum_{i=1}^{n-1} \mathbb{E}[X_i]=(n-1) \frac{{n-2 \choose k-2}}{{n \choose k}}. $$

Answer 3

Hint:

For $i=1,\dots,n$ let $X_i$ be the Bernouilli distributed random variable taking value $1$ if number $i$ is picked out.

Then to be found is: $$\mathbb E(X_1X_2+\cdots+X_{n-1}X_n)$$

Use linearity of independence and symmetry.