Suppose you add two long numbers together. As you work your way toward the result, adding digits from right to left, sometimes you carry a 1 and sometimes you don’t. How often do you carry 1?

Now suppose you add three numbers at a time. Now your carry might be 0, 1, or 2. How often does each appear? How do things change if you’re not working in base 10?

John Holte goes into this problem in detail in [1]. We’ll only look at his first result here.

Suppose we’re adding *m* numbers together in base *b*, with each digit being uniformly distributed. Then at each step of the addition process, the probability distribution of the amount we carry *out* only depends on the amount we carried *in* from the previous step. In other words, the carries form a **Markov chain**!

This means that we can do more than describe the distribution of the amounts carried. We can specify the **transition probabilities** for carries, i.e. the distribution on the amount carried out, conditional on the amount carried in.

## Examples

When we add two base ten numbers, *m* = 2 and *b* = 10, we have the transition matrix

This means that on average, we’re as likely to carry 0 as to carry 1. But more specifically, there’s a 55% chance that we’ll carry a 1 if we carried a 1 on the previous step, and also a 55% chance that we won’t have a carry this time if we didn’t have one last time.

If we add three numbers, things get a little more interesting. Now the transition matrix is

This gives the probabilities of each *out* carry for each *in* carry. We can compute the long run distribution from the matrix above to find that when adding three long numbers, we’ll carry 0 or 1 with probability 1/6 each, and carry 1 with probability 2/3.

When adding three binary numbers, the transition matrix is fairly different than for base 10

but the long run distributions are the same: carry a 1 two thirds of the time, and split the remaining probability equally between carrying 0 and 2.

The transition matrices don’t change much for larger bases; base 100 doesn’t look much different than base 10, for example.

Finally, let’s do an example adding five numbers in base 10. The transition matrix is

and the long run distribution is 1/60, 13/60, 33/60, 13/60, and 1/60 for carries of 0 through 4.

## General case

In general, when adding *m* numbers in base *b*, Holte gives the transition probabilities as

Here is some Python code to compute the transition matrices.

from scipy import floor, zeros, array from scipy.special import comb from numpy.linalg import matrix_power # transition probability def pi(i, j, b, m): s = 0 for r in range(0, j - int(floor(i/b)) + 1): s += (-1)**r * comb(m+1, r) * comb(m-i-1 +b*(j-r+1), m) return s/b**m def transition_matrix(b, m): P = [ [pi(i, j, b, m) for j in range(m)] for i in range(m) ] return array(P)

You can find the long run probabilities by raising the transition matrix to a large power.

## Related posts

[1] John M. Holte. The American Mathematical Monthly, Vol. 104, No. 2 (Feb., 1997), pp. 138-149

I wonder how does this changes when the numbers come from numerical data following the Newcomb-Benford’s law of anomalous numbers, instead of having digits uniformly distributed.

Jakub, here’s my guess. Benford’s law says that digits are roughly uniform in log-space. So here’s a simulation in IDL (you probably never heard of it, but it’s what I use) that does the uniform distribution to recreate the 45/55 matrix and then a log-space distribution. Since small digits are more highly represented in log-space, the probability of carries is smaller. My transition matrix for two numbers is

.84 .76

.15 .23

Here’s the full output of my code and the code itself.

Uniform

0.0998725 0.0995840 0.100013 0.100205 0.100090 0.100240 0.0999095 0.0999435 0.0999900 0.100153

transition matrix

0.549245 0.449910

0.450755 0.550090

Log

0.278547 0.168131 0.121233 0.0945430 0.0775195 0.0659935 0.0570550 0.0507760 0.0453455 0.0408560

transition matrix

0.841960 0.769524

0.158040 0.230476

pro markov_carry

n=1000000

print, ‘Uniform’

;get two sets of uniform distribution of n digits

digits=fix(randomu(seed,n,2)*10)

;validate that the digits are uniform

print, histogram(digits)/(2.0*n)

;create an empty transition matrix

transition=lonarr(2,2)

;loop through each digit and see if the result is greater than 10

;and add to the appropriate part of the transition matrix

prev_carry=0

for i=0,n-1 do begin

carry=(digits[i,0]+digits[i,1]+prev_carry) ge 10

transition[prev_carry,carry]++

prev_carry=carry

end

;print the normalized transition matrix

print, ‘transition matrix’

print, transition/rebin(total(transition,2),2,2)

;now we do the same thing except we pick our digits to

;be uniform in log10 space

print, ‘Log’

digits=fix((10^randomu(seed,n,2)-1)*10/9)

print, histogram(digits)/(2.0*n)

transition=lonarr(2,2)

prev_carry=0

for i=0,n-1 do begin

carry=(digits[i,0]+digits[i,1]+prev_carry) ge 10

transition[prev_carry,carry]++

prev_carry=carry

end

print, ‘transition matrix’

print, transition/rebin(total(transition,1),2,2)

end

John,

Interesting stuff; but I suspect a typo in the 100 number in the following text;

“The transition matrices don’t change much for larger bases; base 100 doesn’t look much different than base 100, for example.”