Associated Topics || Dr. Math Home || Search Dr. Math

### Summing Activity Leads to a Mean of e

```Date: 04/01/2005 at 11:08:24
From: Steve
Subject: I keep getting e as the result of a class activity, why?

I asked my students to keep adding random integers from 1 to 100 until
the sum exceeded 100.  We then found the average number of terms
added.  The answer seems to be e.  Why?  The more we do it, the closer
we get.

I can't find a way to derive this result, although it seems plausible.
I tried using the expansion for e as a sum of reciprocals of
factorials.  I guess this is related to the probability, but I'm not
quite sure.

```

```
Date: 04/04/2005 at 12:27:51
From: Doctor Rick
Subject: Re: I keep getting e as the result of a class activity, why?

Hi, Steve.

This is an interesting question!  My working hypothesis is that the
theoretical mean may be (1 + 1/N)^N, or close to this, for the
generalized experiment in which you add random numbers from 1 through
N until the sum is greater than N.  In the limit as N increases
infinitely, this value equals e.  For N = 100, it is 2.7048.

As a start to understanding this problem, I considered a much simpler
case.  I let N = 4, so that we are choosing numbers from 1 to 4 and
stopping when the sum exceeds 4.  There are few enough possibilities
that I can enumerate them.

There is no way that one number can exceed a sum of 4.  There are 10
ways that the first two numbers chosen can have a sum greater than 4:

14, 23, 24, 32, 33, 34, 41, 42, 43, 44

Each has a probability of 1/4^2 = 1/16, since there are 4^2 ways to
choose two numbers and each has equal probability.  Thus P(2), the
probability that after two numbers the total exceeds 4, is 10/16.

There are 20 ways to choose three numbers such that the first two sum
to 4 or less and the third takes the sum above 4:

113, 114, 122, 123, 124, 131, 132, 133, 134, 212,
213, 214, 221, 222, 223, 224, 311, 312, 313, 314

The probability of each is (1/4)^3 = 1/64, thus P(3) = 20/64.

There are 15 ways to choose four numbers such that the first three
sum to 4 or less and the fourth takes the sum above 4:

1112, 1113, 1114, 1121, 1122, 1123, 1124, 1211,
1212, 1213, 1214, 2111, 2112, 2113, 2114

The probability of each is (1/4)^4 = 1/256, so P(4) = 15/256.

The only possibility left is 1111, in which case any choice for the
fifth number will put the sum over 4.  The probability of getting 1111
is 1/256, so that is P(5), the probability that it will take 5
numbers to exceed a total of 4.

The mean number of selections required to exceed a total of 4 is

2*P(2) + 3*P(3) + 4*P(4) + 5*P(5) =
2*10/16 + 3*20/64 + 4*15/256 + 5*1/256 =
(2*10*4^2 + 3*20*4 + 4*15 + 5*1)/256 =
625/256 =
2.44140625

That's exactly 5^4/4^4 = (1 + 1/4)^4, which is what I was hoping I'd
find.  Perhaps I'm on the right track.  However, another Math Doctor,
Dr. George, has let me know that he did an experiment (like yours, I
assume) where N = 10, and he did not get a mean of (1 + 1/10)^10.

Dr. George had some other very helpful information, though.  It is a
known result that in the limit as N increases infinitely, the mean
number of terms needed to exceed N is e.  You can read about it here:

MathWorld: Uniform Sum Distribution
http://mathworld.wolfram.com/UniformSumDistribution.html

I need to study that further myself.

- Doctor Rick, The Math Forum
http://mathforum.org/dr.math/

```

```
Date: 04/07/2005 at 09:17:14
From: Doctor George
Subject: Re: I keep getting e as the result of a class activity, why?

Hi Steve,

You can see from Dr. Rick's work that doing an analytical experiment
for N=10 would be a lot of work, so what I did was a computer

I noticed from Dr. Rick's work that he set up his discrete experiment
a little differently than mine.  I then changed my assumptions to
match his and repeated my simulation.  For N=10 I now get a mean of
(1 + 1/10)^10 as Dr. Rick's intuition expected.

- Doctor George, The Math Forum
http://mathforum.org/dr.math/

```

```
Date: 04/11/2005 at 21:41:18
From: Doctor Rick
Subject: Re: I keep getting e as the result of a class activity, why?

Hi, Steve, I'm back!

I haven't had much time to give to this problem, but I think now I can
convince myself (at least) that it's true: If we select random digits
from 1 through N until the sum exceeds N, the mean number of
selections is (1+1/N)^N.  In case you're still interested, here's the
proof.

Let's go back to the case of N=4 and construct a chart.  The number in
the n-th column of the m-th row is the probability that after m
selections, the sum is n.  I will only show the columns 1 through N.

1     2     3     4
------------------------
1  1/4   1/4   1/4   1/4
2  0     1/16  2/16  3/16
3  0     0     1/64  3/64
4  0     0     0     1/256

How did I generate this table?  On the first selection, there is an
equal probabilty of selecting any of the numbers 1 through 4.  On the
second selection, the sum cannot be 1, because the lowest possible
sum is 1+1=2.  The probability that the sum will be 2 is the
probability that the sum after 1 selection is less than 2, times 1/4,
the probability that the second selection will be the number that
makes the total 2.  The same follows for each succeeding entry in the
table.  In general, the probability P(m,n) that the total after m
selections is n, is

P(m,n) = 0                              , n < m
(1/N)Sum (k=1 to n-1) P(k,n-1) , n >= m

Now notice the difference between P(m,n-1) and P(m,n): if n >= m, then

N*P(m,n-1) = Sum(k=1 to n-2) P(k,n-1)

so that

N*P(m,n) = N*P(m,n) + P(m-1,n-1)

and

N^m P(m,n) = N^m P(m,n) + N^(m-1) P(m-1,n-1)

The denominator of each P(m,n) is N^m.  The numerator of P(m,n) is
found by adding the numerators of the cell to its left, P(m,n-1) and
the cell above that, P(m-1,n-1).  This is the rule for Pascal's
triangle, and indeed you can see that the columns in my table are the
rows of Pascal's triangle: 1; 1,1; 1,2,1; 1,3,3,1.  Now the numbers
in Pascal's triangle are combinations; we thus get the formula
(writing C(a,b) for the combinations of "a" things taken "b" at a
time):

P(m,n) = C(n-1,m-1)/N^m     , m <= n   ; 0, m > n

(n-1)!
= -----------------  , m <= n   ; 0, m > n
(m-1)! (n-m)! N^m

How do we use these probabilities to compute the mean number of
selections to make the sum exceed N?  First, the sum of each row of
the table (up through column N) is the probability that the sum has
not yet exceeded N.  The probability that the sum has exceeded N is 1
minus this sum.  The probability that the m-th selection is the first
to put the sum over N, is

P(m) = P(m-th sum exceeds N) - P((m-1)-th sum exceeds N)
= (1 - Sum(n=1 to N)P(m,n)) - (1 - Sum(k=1 to N)P(m-1,n))
= Sum(n=1 to N)P(m-1,n) - Sum(n=1 to N)P(m,n)
= Sum(n=1 to N)(P(m-1,n) - P(m,n))

The probability that the first selection (m=1) puts the sum over N is
zero.  Applying the formula to the table above for N=4, we get

m  P(sum<N)  P(m selections needed to exceed N)
-------------------------------------------------------
1  4/4       0
2  6/16      4/4 - 6/16 = 10/16
3  4/64      6/16 - 4/64 = 20/64
4  1/256     4/64 - 1/256 = 15/256
5  0         1/256 - 0 = 1/256

This agrees with my previous work based on enumerating the
possibilities.  As I did there, I calculate the mean number of terms
needed to exceed N by multiplying each probability in the last column
by m and summing:

1*P(1) + 2*P(2) + 3*P(3) + 4*P(4) + 5*P(5) = 20/16 + 60/64 + 20/256
+ 5/256
= 625/256

In general, the formula is

<m> = Sum(m=2 to N+1) m*Sum(n=1 to N)(P(m-1,n) - P(m,n))

The sums can be interchanged, so that instead of summing across the
rows of the table, then add the row sums, we sum first down the
columns, then add the column sums.  We have

<m> = Sum(n=1 to N) Sum(m=2 to N+1) m*(P(m-1,n) - P(m,n))

Examine the inner sum: in the case N = 4, it is

2(P(1,n)-P(2,n)) + 3(P(2,n)-P(3,n)) + 4(P(3,n)-P(4,n)) + 5(P(4,n) -
P(5,n)) =

2P(1,n) - 2P(2,n)
+ 3P(2,n) - 3P(3,n)
+ 4P(3,n) - 4P(4,n)
+ 5P(4,n) - 5P(5,n)
-----------------------------------------------
2P(1,n) + P(2,n)  + P(3,n)  + P(4,n)  - 5P(5,n)

In general, with P(1,n) = 1/N and P(N+1,n) = 0, this is

1/N + Sum(m=1 to N)P(m,n)

The full sum is

<m> = Sum(n=1 to N)(1/N + Sum(m=1 to N)P(m,n))
= 1 + Sum(n=1 to N) Sum(m=1 to N) P(m,n)
= 1 + Sum(n=1 to N) Sum(m=1 to n) C(n-1,m-1)/N^m

I changed the summation limit in the last step because P(m,n) = 0 for
m > n.

Recall that the expansion of (1 + 1/N)^n is

(1 + a)^n = C(n,0) + C(n,1)a + C(n,2)a^2 + ... + C(n,n)a^n

Comparing the following expansion with the sum over m, we see they
are equal:

(1 + 1/N)^(n-1)/N = (C(n-1,0) + C(n-1,1)/N + ... + C(n-1,n-1)/N^(n-
1))/N
= C(n-1,0)/N + C(n-1,1)/N^2 + ... + C(n-1,n-1)/N^n

Using this result, our formula for the mean is now

<m> = 1 + (1/N)Sum(n=1 to N)(1 + 1/N)^(n-1)
= 1 + (1/N)Sum(n=0 to N-1)(1 + 1/N)^n

The remaining sum is a geometric series, and we can apply the formula

Sum(k=0 to n) a^k = (a^(n+1)-1)/(a-1)

to get

<m> = 1 + (1/N)((1 + 1/N)^N - 1)/((1 + 1/N) - 1)
= 1 + (1/N)((1 + 1/N)^N - 1)/(1/N)
= 1 + (1 + 1/N)^N - 1
= (1 + 1/N)^N

That's what I've been trying to show!  It's not the tightest proof in
the world, but I can rest content.  Thanks for bringing up an
interesting problem.

- Doctor Rick, The Math Forum
http://mathforum.org/dr.math/

```

```
Date: 04/12/2005 at 07:59:06
From: Steve
Subject: Thank you (I keep getting e as the result of a class
activity, why?)

Wow.  Thanks for all your effort.  I'll sift through your proof this
weekend.  I'm glad to see that this actually works.  Now I have to try
to explain it to my students.  Thanks again for all your work.

Steve
```
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search