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

• This (the edit) does make the handling quite a bit less smooth. In my approach for example, the conditional probabilities $P(r(X)=r|X=x)$ get messy. – Christian Remling Feb 25 '15 at 20:14

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

• As stated, you pick $k$ distinct numbers out of $[1,n]$. (this goes also to other answers): I am kind of overloaded at the moment and it could take a few days to process all the answers and tick the best one. – Matjaž Krnc Feb 27 '15 at 10:17
• In general, I really like the generating function approach. Could you briefly give some hint about your first equation above (about $\mathbb{E}(t^{X_j})$)? – Matjaž Krnc Feb 28 '15 at 9:42
• The combinatorial reason is that ${ 1\over 1-x}$ resp. ${x \over 1-x}$ are the exp. generating functions for ordered resp. non-empty ordered sets (sequences). But you can simply extract coefficients and argue directly to see that its true. – esg Feb 28 '15 at 13:38

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?

• At a glance, this seems a nice way to go! I just hope that those sums are somehow reducable. Thans a lot! – Matjaž Krnc Feb 28 '15 at 9:33

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

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

• Ooops! I screwed-up, didn't I. – Liviu Nicolaescu Feb 25 '15 at 17:44
• Thank you for your continuous and discrete approach. As you know, for $i\in [1,k]$, numbers $\alpha_i$ as well as $x_i$ (in your notation), must be distinct. Is it maybe more correct, to write $$P_{j}(\ell)=\frac{1}{n^{\underline{k}}}\sum_{s\geq j}\binom{k}{s}\ell^{\underline{s}}(n-\ell)^{\underline{k-s}}?$$ – Matjaž Krnc Feb 28 '15 at 9:58