1
$\begingroup$

I'm reading this paper An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs. Which is solving a makespan minimizing job-shop problem for Poisson job sizes. Basically, schedule the minimum work for random job sizes whose job size distributions are Poissonian. The authors give an equation that I hadn't seen before:

$$\mathbb{E} \left[ \text{max}(X,Y) \right] = \sum_{x=0}^\infty \Pr\{X=x\} \left\{ x + \sum_{y=x+1}^\infty \Pr\{Y \geq y\} \right\}, $$ where $X$ and $Y$ are both random (independent) variables on support $\{0,1,\dots\}$.

I can think of one general approach (conditional expectations) that seems reasonable to derive this but I'm not able to get the result.

Can someone derive this result?

Note: I'll accept any derivation, the approach need not use conditional expectations. I only mention because it seems like this is a conditional expectation identity.

$\endgroup$
2
$\begingroup$

Let $Z \in \{0,1,\dots\}$ be a nonnegative discrete random variable. Then, we have $$ \mathbb E[ Z ]= \sum_{z = 1}^\infty \mathbb P(Z \ge z). $$ Try to prove this yourself --------------------------------------------------------------------------------------- Hint: $Z = \sum_{z=1}^\infty (\cdots)$..

Let $Z = \max(X,Y)$. Then, \begin{align} \mathbb E[\max(X,Y)] &= \sum_{z=1}^\infty \mathbb P(\max(X,Y) \ge z) \\ &=\sum_{z=1}^\infty \sum_{x=0}^\infty \mathbb P(X = x) \mathbb P(\max(x,Y) \ge z \mid X = x) \\ &=\sum_{x=0}^\infty \mathbb P(X = x) \Big[ \sum_{z=1}^\infty \mathbb P(\max(x,Y) \ge z)\Big] \quad \text{(by indept.)} \\ &=\sum_{x=0}^\infty \mathbb P(X = x) \Big[ x + \sum_{z=x+1}^\infty \mathbb P(Y \ge z)\Big]. \end{align}

$\endgroup$
1
  • 1
    $\begingroup$ thanks, I had missed the reasoning on the line using the independence criteria. $\endgroup$ – Lucas Roberts Jan 2 at 17:56

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.