Expected value of a function over random sets

Question

I am doing an analysis on the complexity of some set-related algorithm where the input is a random set. One of my setbacks can be formulated as follows:

Pick $k$ distinct numbers out of numbers $[1,n]$ uniformly at random, order them increasingly by size and denote them with $\alpha_1, \alpha_2, \dots , \alpha_k$.

I would like to calculate $$\mu:=\mathrm{E}\left(\sum_{i=1}^{k}\left(\frac{1}{2}\right)^{\alpha_{i}-i}\right),$$ or at least find a good upperbound to it. Trivial bounds are obviously $$k\cdot 2^{k-n} \leq \mu \leq k.$$

EDIT: I am sorry for not being clear enough. In my problem, all chosen numbers are integers (not reals). Hopefully there is not much difference when using just integers.

Answer 1

I assume you mean picking a random $k$-subset from {1,...,n}, i.e. drawing without replacement? In this case one finds for $X_j=\alpha_j-j$ that

$$\mathbb{E}(t^{X_j})= {k!\,(n-k)! \over n!} [x^{n-k}]{1 \over (1-tx)^j(1-x)^{k+1-j}}$$

and $$\mu(t):=\mathbb{E} \sum_{j=1}^k t^{X_j}={n+1 \over n+1-k}{1-t^{n+1-k} \over 1-t}- t\,{1-t^{n-k} \over 1-t} -1={k \over n-k+1}{1-t^{n-k+1} \over 1-t}$$

Answer 2

For $1 \leq j \leq n$, define the random variable $X_j(S)$ by $X_j(S) = 0$ if $j$ is not in $S$, and $X_j(S) = (.5)^{j - i}$ if $j$ is the $i$th entry of $S$. Then your random function is the sum of the $X_j$'s, and one gets:

$$\mu = \frac{1}{\binom{n}{k}}\sum_{j = 1}^{n}\sum_{i = 1}^k \left(\frac{1}{2}\right)^{j - i}\binom{j-1}{i-1}\binom{n - j}{k - i}$$

Maybe this helps?

Answer 3

We can write $\mu = E\sum 2^{r(X_j)-X_j}$, where $X_j$ is the $j$th number drawn and $r(X_j)$ is its rank after ordering. By linearity of the expectation, since the $(X_j,r(X_j))$ have the same distribution, $\mu = k E2^{r(X_1)-X_1}$. To evaluate this expectation, I condition on $X_1$; notice that if $X_1=x$, then I need exactly $r-1$ of the other points $X_2,\ldots ,X_k$ in $[1,x]$ to have $r(X_1)=r$. Thus $$ \mu= \frac{k}{n-1} \sum_{r=1}^k 2^r \binom{k-1}{r-1} \int_1^n \left(\frac{x-1}{n-1} \right)^{r-1} \left( 1- \frac{x-1}{n-1} \right)^{k-r} 2^{-x}\, dx . $$ I substitute $t=x-1$, and the sum can be evaluated with the binomial theorem. This gives $$ \mu = \frac{k}{n-1} \int_0^{n-1} \left( 1 + \frac{t}{n-1}\right)^{k-1} 2^{-t}\, dt . $$

Answer 4

Denote by $x_1,\dotsc, x_k$ the random real numbers that you chose. Define the random numbers

$$ y_j= \frac{1}{n-1}(x_j-1), $$

so that $y_j$ is uniformly distributed in $[0,1]$. We have

$$ x_j= (n-1) y_j+1. $$

Denote by $t_j$ the numbers $y_j$ rearranged in increasing order. Then

$$ \alpha_j =(n-1)t_j+1, $$

and for any $r>0$ we have

$$ r^{\alpha_j-j}= r^{(n-1)t_j+1-j}. $$

The random variables $t_j$ are distributed according to the Beta distribution

$$ f_j(t)dt =\frac{k!}{(k-1)!(k-j)!} t^{j-1}(1-t)^{k-j}dt. $$

We have $\newcommand{\bE}{\mathbb{E}}$

$$\bE(r^{\alpha_j-j})= \frac{r^{1-j}k!}{(j-1)! (k-j)!}\int_0^1 r^{(n-1)t} t^{j-1}(1-t)^{k-j}dt $$

$$= \frac{k!}{(j-1)! (k-j)!}\int_0^1 r^{(n-1)t} \left(\frac{t}{r}\right)^{j-1}(1-t)^{k-j}dt $$

$$=k\binom{k-1}{j-1}\int_0^1 r^{(n-1)t} \left(\frac{t}{r}\right)^{j-1}(1-t)^{k-j}dt. $$

$$\sum_{j=1}^k \bE(r^{\alpha_j-j})=k\int_0^1 r^{(n-1)t}\left(\sum_{j=1}^k \binom{k-1}{j-1}\left(\frac{t}{r}\right)^{j-1}(1-t)^{k-j}\right)dt $$

$$= k \int_0^1 r^{(n-1)t} \left(1 +\frac{t}{r}-t\right)^{k-1} dt. $$

Thus we have to compute an integral of the form

$$\int_0^1 e^{\lambda t}(1+at)^k-1 dt,\;\;\lambda, a\in\mathbb{R},\;\;a\neq 0. $$

If we make the change in variables $s= 1+at$, this integral becomes

$$ \frac{1}{a} \int_1^{a+1} e^{\lambda\frac{s-1}{a}} s^{k-1} ds=\frac{1}{ae^{\lambda/a} }\int_1^{a+1} e^{\frac{\lambda}{a} s} s^{k-1} ds. $$

The last integral can be computed integrating by parts.

Remark. When the numbers $x_1,\dotsc, x_k$ are integers one thing goes horrible wrong: the probability that two of the numbers are equal is not zero. However you can still find the distribution of $\alpha_j$. For $\ell=1,\dotsc, n$, $P(\alpha_j\leq \ell)$ is the probability that at least $j$ of the numbers $x_1,\dotsc, x_k$ are $\leq \ell$ which is

$$ P_j(\ell)=\frac{1}{n^k}\sum_{s\geq j} \binom{k}{s}\ell^s(n-\ell)^{k-s}. $$

This allows you to find a formula for the expectation of $r^{\alpha_j}$. Note that the function

$$ r\mapsto P_j(r):=\bE(r^{\alpha_j}) $$

is the probability generating function of the random variable $\alpha_j$. In this case it is a polynomial of degree $n$ in $r$. More precisely

$$ P_j(r)= \sum_{\ell=1}^n r^\ell\Bigl(P_j(\ell)-P_j(\ell-1)\Bigr). $$

Hence $$ \bE(r^{\alpha_j-j})=\sum_{j=1}^k \sum_{\ell=1}^n r^{\ell-j}\Bigl( P_j(\ell)-P_j(\ell-1)\Bigr). $$