# Expected value of max of two discrete random variables

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.

## 1 Answer

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}

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