Background
If one assumes that servers $X_1$ and $X_2$ has exponential service
times with rate $\lambda_1$ and $\lambda_2$ respectively, (i.e.
$X_i \sim \Exp(\lambda_i), i = 1,2$), then one can follow the
standard arguments and say that the waiting time $\min\left\{ X_1,
X_2 \right\} \sim \Exp(\lambda_1 + \lambda_2)$, so the expected
waiting time is $1/(\lambda_1 + \lambda_2)$.
Problem
I tried finding the expected waiting time by conditioning on $X_1 - X_2$.
\begin{equation}
\begin{split}
& \Pr(X_1 > X_2) \\
=& \int_{0}^{\infty} p_{X_1}(x_1) \Pr(X_2 < x_1) \ud x_1 \\
=& \int_{0}^{\infty} \lambda_1 e^{-\lambda_1 x_1} (1 -
e^{-\lambda_2 x_1}) \ud x_1 \\
=& \int_{0}^{\infty} \lambda_1 e^{-\lambda_1 x_1} \ud x_1 -
\int_{0}^{\infty} \lambda_1 e^{-(\lambda_1 + \lambda_2) x_1} \ud
x_1 \\
=& 1 + \left. \frac{\lambda_1}{\lambda_1 + \lambda_2}
e^{-(\lambda_1 + \lambda_2) x_1} \right|_{0}^{\infty} \\
=& 1 - \frac{\lambda_1}{\lambda_1 + \lambda_2} \\
=& \frac{\lambda_2}{\lambda_1 + \lambda_2}
\end{split}
\label{eq:pr_min}
\end{equation}
Similarly, one has $\Pr(X_1 \le X_2) = \lambda_1/(\lambda_1 +
\lambda_2)$.
\begin{equation}
\begin{split}
& \E[\left\{ X_1, X_2 \right\}] \\
=& \E[\min\left\{ X_1, X_2 \right\} \mid X_1 > X_2] \Pr(X_1 > X_2)
\\
+& \E[\min\left\{ X_1, X_2 \right\} \mid X_1 \le X_2] \Pr(X_1 \le X_2)
\\
=& \E[X_2] \Pr(X_1 > X_2) + \E[X_1] \Pr(X_1 \le X_2) \\
=& \frac{1}{\lambda_2} \frac{\lambda_2}{\lambda_1 + \lambda_2} +
\frac{1}{\lambda_1} \frac{\lambda_1}{\lambda_2 + \lambda_1} \\
=& \frac{2}{\lambda_1 + \lambda_2}
\end{split}
\label{eq:wrong}
\end{equation}
This is different from what we expect. What’s wrong with the
above calculation?
Solution
I really thought about the meaning of $\E[\min\left\{ X_1, X_2
\right\} \mid X_1 > X_2]$, and find out that this conditional
expectation won’t be helpful because
\[
\E[\min\left\{ X_1, X_2 \right\} \mid X_1 > X_2] =
\frac{\int_{0}^{\infty} \int_{0}^{x_1} x_2 \ud x_2 \ud x_1}{\Pr(X_1
> X_2)}
\]
Actually, one can divide it into two halves.
\begin{equation}
\begin{split}
& \E[\min\left\{ X_1, X_2 \right\}] \\
=& \int_{0}^{\infty} \int_{0}^{x_1} x_2 \lambda_1 \lambda_2
e^{-\lambda_1 x_1 - \lambda_2 x_2} \ud x_2 \ud x_1 \\
+& \int_{0}^{\infty} \int_{0}^{x_2} x_1 \lambda_2 \lambda_1
e^{-\lambda_2 x_2 - \lambda_1 x_1} \ud x_1 \ud x_2
\end{split}
\label{eq:head}
\end{equation}
By observing the symmetry between the subscripts ‘1’ and ‘2’ in the
above equation, we only need to evaluate one of them.
\begin{equation}
\begin{split}
& \int_{0}^{\infty} \int_{0}^{x_1} x_2 \lambda_1 \lambda_2
e^{-\lambda_1 x_1 - \lambda_2 x_2} \ud x_2 \ud x_1 \\
=& \int_{0}^{\infty} \lambda_1 \lambda_2 e^{-\lambda_1 x_1} \left(
\int_{0}^{x_1} x_2 e^{-\lambda_2 x_2} \ud x_2 \right) \ud x_1 \\
=& \int_{0}^{\infty} \lambda_1 \lambda_2 e^{-\lambda_1 x_1} \left(
\left. -x_2 \cdot \frac{e^{-\lambda_2 x_2}}{\lambda_2}
\right|_{x_2 = 0}^{x_2 = x_1} + \int_{0}^{x_1} \frac{e^{-\lambda_2
x_2}}{\lambda_2} \ud x_2 \right) \ud x_1 \\
=& \int_{0}^{\infty} \lambda_1 \lambda_2 e^{-\lambda_1 x_1} \left(
-x_1 \cdot \frac{e^{-\lambda_2 x_1}}{\lambda_2} - \left.
\frac{e^{-\lambda_2 x_2}}{\lambda_2^2} \right|_{x_2 = 0}^{x_2 =
x_1} \right) \ud x_1 \\
=& \int_{0}^{\infty} \lambda_1 \lambda_2 e^{-\lambda_1 x_1} \left(
-x_1 \cdot \frac{e^{-\lambda_2 x_1}}{\lambda_2} + \frac{1 -
e^{-\lambda_2 x_1}}{\lambda_2^2} \right) \ud x_1 \\
=& \int_{0}^{\infty} -\lambda_1 x_1 e^{-(\lambda_1 + \lambda_2)
x_1} \ud x_1 + \int_{0}^{\infty} \frac{\lambda_1}{\lambda_2}
(e^{-\lambda_1 x_1} - e^{-(\lambda_1 + \lambda_2) x_1}) \ud x_1
\\
=& \lambda_1 \left( \left. \frac{x_1 e^{-(\lambda_1 + \lambda_2)
x_1}}{\lambda_1 + \lambda_2} \right|_{0}^{\infty} -
\int_{0}^{\infty} \frac{e^{-(\lambda_1 + \lambda_2)
x_1}}{\lambda_1 + \lambda_2} \right) \\
+& \frac{\lambda_1}{\lambda_2} \left( \left. -\frac{e^{\lambda_1
x_1}}{\lambda_1} \right|_{0}^{\infty} + \left.
\frac{e^{-(\lambda_1 + \lambda_2) x_1}}{\lambda_1 + \lambda_2}
\right|_{0}^{\infty} \right) \\
=& \lambda_1 \left( 0 + \left. \frac{e^{-(\lambda_1 + \lambda_2)
x_1}}{(\lambda_1 + \lambda_2)^2} \right|_{0}^{\infty} \right) +
\frac{\lambda_1}{\lambda_2} \left( \frac{1}{\lambda_1} -
\frac{1}{\lambda_1 + \lambda_2} \right) \\
=& -\frac{\lambda_1}{(\lambda_1 + \lambda_2)^2} +
\frac{1}{\lambda_2} - \frac{\lambda_1}{\lambda_2 (\lambda_1 +
\lambda_2)}
\end{split}
\label{eq:half_int}
\end{equation}
Similarly, one has
\begin{equation}
\begin{split}
& \int_{0}^{\infty} \int_{0}^{x_2} x_1 \lambda_2 \lambda_1
e^{-\lambda_2 x_2 - \lambda_1 x_1} \ud x_1 \ud x_2 \\
=& -\frac{\lambda_2}{(\lambda_2 + \lambda_1)^2} +
\frac{1}{\lambda_1} - \frac{\lambda_2}{\lambda_1 (\lambda_2 +
\lambda_1)}.
\end{split}
\label{eq:half_int2}
\end{equation}
Substitute \eqref{eq:half_int} and \eqref{eq:half_int2} into
\eqref{eq:head}.
\begin{equation}
\begin{split}
& \E[\min\left\{ X_1, X_2 \right\}] \\
=& \left( -\frac{\lambda_1}{(\lambda_1 + \lambda_2)^2} +
\frac{1}{\lambda_2} - \frac{\lambda_1}{\lambda_2 (\lambda_1 +
\lambda_2)} \right) \\
+& \left( -\frac{\lambda_2}{(\lambda_2 + \lambda_1)^2} +
\frac{1}{\lambda_1} - \frac{\lambda_2}{\lambda_1 (\lambda_2 +
\lambda_1)} \right) \\
=& -\left( \frac{\lambda_1}{(\lambda_2 + \lambda_1)^2} +
\frac{\lambda_2}{(\lambda_2 + \lambda_1)^2} \right) + \left(
\frac{1}{\lambda_1} + \frac{1}{\lambda_2} \right) \\
-& \left( \frac{\lambda_1}{\lambda_2 (\lambda_1 + \lambda_2)} +
\frac{\lambda_2}{\lambda_1 (\lambda_2 + \lambda_1)} \right) \\
=& -\frac{1}{\lambda_1 + \lambda_2} + \frac{\lambda_1 +
\lambda_2}{\lambda_1 \lambda_2} - \frac{\lambda_1^2 +
\lambda_2^2}{\lambda_1 \lambda_2 (\lambda_1 + \lambda_2)} \\
=& -\frac{1}{\lambda_1 + \lambda_2} + \frac{(\lambda_1 +
\lambda_2)^2 - (\lambda_1^2 + \lambda_2^2)}{\lambda_1 \lambda_2
(\lambda_1 + \lambda_2)} \\
=& -\frac{1}{\lambda_1 + \lambda_2} + \frac{2\lambda_1
\lambda_2}{\lambda_1 \lambda_2 (\lambda_1 + \lambda_2)} \\
=& -\frac{1}{\lambda_1 + \lambda_2} + \frac{2}{\lambda_1 +
\lambda_2} \\
=& \frac{1}{\lambda_1 + \lambda_2}
\end{split}
\label{eq:fin}
\end{equation}
This is consistent with what we expect. I finally understand what’s
wrong in \eqref{eq:wrong}: $X_1$ isn’t independent from $X_1 -
X_2$.
Generalization
By induction, we can generalize \eqref{eq:fin} to the expected waiting
time for $n$ servers in parallel: if $X_i \sim \Exp(\lambda_i)
\,\forall 1 \le i \le n$, then
\[
\E[\min\left\{ X_1, \ldots, X_n \right\}]
= \frac{1}{\sum\limits_{k = 1}^n \lambda_k}.
\]