  The standard approach to realize a quantum repeater relies upon probabilistic
but heralded entangled state manipulations and the storage of quantum states
while waiting for successful events. In the literature on this class of
repeaters, calculating repeater rates has typically depended on approximations
assuming sufficiently small probabilities. Here we propose an exact and
systematic approach including an algorithm based on Markov chain theory to
compute the average waiting time (and hence the transmission rates) of quantum
repeaters with arbitrary numbers of links. For up to four repeater segments, we
explicitly give the exact rate formulae for arbitrary entanglement swapping
probabilities. Starting with three segments, we explore schemes with arbitrary
(not only doubling) and dynamical (not only predetermined) connections. The
effect of finite memory times is also considered and the relative influence of
the classical communication (of heralded signals) is shown to grow
significantly for larger probabilities. Conversely, we demonstrate that for
small swapping probabilities the statistical behavior of the waiting time in a
quantum repeater cannot be characterized by its average value alone and
additional statistical quantifiers are needed. For large repeater systems, we
propose a recursive approach based on exactly but still efficiently computable
waiting times of sufficiently small sub-repeaters. This approach leads to
better lower bounds on repeater rates compared to existing schemes.
