of being at j is the same as being at —j. Computing E(|5

n

|) is not

so easy; however, it is straightforward to calculate E(S^). Note that

E ( ^ ) = E[(X1

+

.-. + Xn)2}

= !(*?)+x;E(xixj).

. 7 = 1 i^3

Since X] = 1 and E(XiXj) = E(Xi)E(Xj) = 0iii^j, we see that

E ( S

2

) = n .

This says that the expected squared distance is n, and we can infer

(at least informally) that the expected distance should be of order

yjn (it is actually about Cy/n for a constant c different than 1).

Where do we expect to be after n steps? Since the walker always

moves from an even integer to an odd integer or from an odd integer

to an even integer, we know for sure that we are at an even integer if

n is even or an odd integer if n is odd. Let us suppose that we have

gone 2n steps, and ask what is the probability that we are at the

even integer 2j. Using the binomial distribution, we can determine

the probability exactly. There are 22n different sequences of +l's

and — l's of length 2n. Each one has probability 2 _ 2 n of occurring.

In order for ^ n to equal 2j we need n + j moves to the right (+1)

and n — j moves to the left (—1). The number of sequences with

n + j "+l"s and n — j "—l"s is given by the appropriate binomial

coefficient. Hence

2 M o - 2 » _

0

- 2 n (2n)!

P{52„ = 2j} = , . 2 - ^ = 2

\n + jj {n + j)\{n-j)\

In particular,

P

{

5

2 n

= 0} = 2 - 2 " ^ .

n\n\

This is a nice exact expression. Unfortunately, it is not so easy to see

how big or small it is. What we need is an approximate formula for

n\. There is such a formula, first published by J. Stirling in 1730 and

now known as Stirling's formula. It is our goal here to see how this

formula can be derived.

n

|) is not

so easy; however, it is straightforward to calculate E(S^). Note that

E ( ^ ) = E[(X1

+

.-. + Xn)2}

= !(*?)+x;E(xixj).

. 7 = 1 i^3

Since X] = 1 and E(XiXj) = E(Xi)E(Xj) = 0iii^j, we see that

E ( S

2

) = n .

This says that the expected squared distance is n, and we can infer

(at least informally) that the expected distance should be of order

yjn (it is actually about Cy/n for a constant c different than 1).

Where do we expect to be after n steps? Since the walker always

moves from an even integer to an odd integer or from an odd integer

to an even integer, we know for sure that we are at an even integer if

n is even or an odd integer if n is odd. Let us suppose that we have

gone 2n steps, and ask what is the probability that we are at the

even integer 2j. Using the binomial distribution, we can determine

the probability exactly. There are 22n different sequences of +l's

and — l's of length 2n. Each one has probability 2 _ 2 n of occurring.

In order for ^ n to equal 2j we need n + j moves to the right (+1)

and n — j moves to the left (—1). The number of sequences with

n + j "+l"s and n — j "—l"s is given by the appropriate binomial

coefficient. Hence

2 M o - 2 » _

0

- 2 n (2n)!

P{52„ = 2j} = , . 2 - ^ = 2

\n + jj {n + j)\{n-j)\

In particular,

P

{

5

2 n

= 0} = 2 - 2 " ^ .

n\n\

This is a nice exact expression. Unfortunately, it is not so easy to see

how big or small it is. What we need is an approximate formula for

n\. There is such a formula, first published by J. Stirling in 1730 and

now known as Stirling's formula. It is our goal here to see how this

formula can be derived.