6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Christian Remling Feb 25 '15 at 20:14
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Matjaž Krnc Feb 27 '15 at 10:17
  • $\begingroup$ 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})$)? $\endgroup$ – Matjaž Krnc Feb 28 '15 at 9:42
  • 1
    $\begingroup$ 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. $\endgroup$ – esg Feb 28 '15 at 13:38
2
$\begingroup$

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?

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

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

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Ooops! I screwed-up, didn't I. $\endgroup$ – Liviu Nicolaescu Feb 25 '15 at 17:44
  • $\begingroup$ 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}}? $$ $\endgroup$ – Matjaž Krnc Feb 28 '15 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.