1
$\begingroup$

What's the expected value of the expression: $x^{random(y, y+1)}$ where $random(a,b)$ is a uniformly random real number between a and b.

Simple testing confirms my suspicion that this is not simply $x^{E[random(y, y+1)]}$, i.e. $x^{y+0.5}$.

(I'm coming up with some exponential backoff retry logic for a system that involves this randomization to prevent "collisions", and I'm trying to analyze its expected cumulative retry time.)

2 Answers 2

1

The expected value of $f(X)$ for some random variable $X$ is calculated as follows: $\mathbb{E}(f(X)) = \int f(x)p(x)dx$ for $p$ the probability density function associated to $X$.

In your case we have: $\mathbb{E} x^n = \int_y^{y+1} x^n dn = \left[\frac{1}{\log x}x^n\right]^{y+1}_y = \frac{1}{\log x}\left(x^{y+1}-x^y\right)$

  • 0
    $\int x^n\,dn\ne(1/(n+1))x^{n+1}$.2011-06-06
  • 0
    Yeah, you're right. I changed it. Bit too used to x as a variable...2011-06-06
  • 0
    Thanks, Shai Covo's answer was also useful (explicitly stating what $p(x)$ in your equation resolved to). But this answer actually stated the final formula. Let me just make sure and test this...2011-06-06
  • 0
    @Maian: I already tested it, and it is correct.2011-06-06
  • 0
    Okay, I just tested it too :)2011-06-06
1

If $Z$ is a uniform random variable on $(y,y+1)$, then it has density function $f_Z$ given by $f_Z (s) = 1$ if $y < s < y+1$, and $f_Z (s) = 0$ otherwise. Thus, $$ {\rm E}[x^Z ] = \int {x^s f_Z (s)ds} = \int_y^{y + 1} {x^s ds} = \ldots . $$

  • 0
    Is $f_Z(s)=1$ because $y-(y+1)=1$? I thought the pdf of a uniform distribution was $1/(b-a)$ where for $a (or something like that).2011-06-06
  • 0
    You're exactly right. $f_z(s) = \frac{1}{(y+1)-y} = 1$ here.2011-06-06
  • 0
    @Maian: Indeed, $f_Z (s) = 1$ (for $y < s < y+1$) because $(y+1)-y=1$ (here $a=y$ and $b=y+1$, hence $1/(b-a)=1$).2011-06-06