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

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.

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

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

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 by size and denote them with $\alpha_1, \alpha_2, \dots , \alpha_k$, such that $\alpha_i < \alpha_{i+1}$ for $i\in [1,k-1]$.

I would like to calculate $$\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.

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