Expected value of max of two discrete random variables

Question

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.

Answer 1

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}