Expected value of a function over random sets 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. 
 A: 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?
A: 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). $$
A: 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 .
$$
A: 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}$$
