Retrying Packets on a Lossy Link

When packets get lost, the sender retries until one gets through. The expected number of tries is an infinite series. The ratio of neighboring terms tends to the loss probability p, so whenever p < 1 the ratio test guarantees a finite answer: 1/(1 − p) tries on average.

How it works

The ratio test

In one sentence

If $\lim\left|\frac{a_{n+1}}{a_n}\right| = L$ , the series $\sum a_n$ converges absolutely when $L < 1$ , diverges when $L > 1$ , and the test is inconclusive when $L = 1$ . The root test uses $\lim\sqrt[n]{|a_n|}$ the same way.

General formula

E[{\htmlData{sym=0}{N}}] = \sum_{{\htmlData{sym=2}{n}}=1}^{\infty} {\htmlData{sym=2}{n}}\,{\htmlData{sym=1}{p}}^{{\htmlData{sym=2}{n}}-1}(1-{\htmlData{sym=1}{p}}), \qquad \lim_{{\htmlData{sym=2}{n}}\to\infty}\frac{a_{{\htmlData{sym=2}{n}}+1}}{{\htmlData{sym=3}{a_n}}} = \lim_{{\htmlData{sym=2}{n}}\to\infty}\frac{{\htmlData{sym=2}{n}}+1}{\htmlData{sym=2}{{n}}}\,{\htmlData{sym=1}{p}} = {\htmlData{sym=1}{p}} < 1

If each term is eventually about $L$ times the last, the tail behaves like a geometric series with ratio $L$ , which converges exactly when $L < 1$ .

What the symbols mean

$N$
Tries
How many sends until one gets through.
$p$
Loss probability
Chance a single send is lost.
$n$
Try number
Which attempt finally succeeds.
$a_n$
Term
The nth term of the series: n p^(n−1)(1 − p).

The first success happens on try $n$ with probability $p^{n-1}(1-p)$ : $n - 1$ losses, then a success.
The expected number of tries is $\sum n\,p^{n-1}(1-p)$ .
The ratio of neighboring terms is $\frac{n+1}{n}p \to p$ . Since $p < 1$ , the ratio test says the series converges.
Its sum is $\frac{1}{1-p}$ : at 50% loss, 2 tries on average; at 90%, 10.

Learn the math

The Ratio TestCalc II · Lesson 33, Sequences and Series The Root TestCalc II · Lesson 34, Sequences and Series Strategy for SeriesCalc II · Lesson 35, Sequences and Series