  We consider the delay of network coding compared to routing with
retransmissions in packet erasure networks with probabilistic erasures. We
investigate the sub-linear term in the block delay required for unicasting $n$
packets and show that there is an unbounded gap between network coding and
routing. In particular, we show that delay benefit of network coding scales at
least as $\sqrt{n}$. Our analysis of the delay function for the routing
strategy involves a major technical challenge of computing the expectation of
the maximum of two negative binomial random variables. This problem has been
studied previously and we derive the first exact characterization which may be
of independent interest. We also use a martingale bounded differences argument
to show that the actual coding delay is tightly concentrated around its
expectation.
