“Random Walk--1-D”的概念、定义、习题解题方法及翻译-数学辞典

单词

Random Walk--1-D

释义

Random Walk--1-D

Let steps of equal length be taken along a Line. Let be the probability of taking a step to the right, theprobability of taking a step to the left, the number of steps taken to the right, and the number of steps taken tothe left. The quantities , , , , and are related by

(1)

and

(2)

Now examine the probability of taking exactly

steps out of

to the right. There are

ways of taking

steps to the right and

to the left, where

is a Binomial Coefficient.The probability of taking a particular ordered sequence of

and

steps is

. Therefore,

(3)

where

is a Factorial. This is a Binomial Distribution and satisfies

(4)

The Mean number of steps

to the right is then

(5)

but

(6)



			(7)

From the Binomial Theorem,

(8)

The Variance is given by

(9)

But

(10)

(11)

and








			(12)

Therefore,

(13)

and the Root-Mean-Square deviation is

(14)

For a large number of total steps

, the Binomial Distribution characterizing the distribution approaches a Gaussian Distribution.

Consider now the distribution of the distances traveled after a given number of steps,

(15)

as opposed to the number of steps in a given direction. The above plots show

for

and three values

, and

, respectively. Clearly, weighting the steps toward one direction or the other influences theoverall trend, but there is still a great deal of random scatter, as emphasized by the plot below, which shows three randomwalks all with

Surprisingly, the most probable number of sign changes in a walk is 0, followed by 1, then 2,etc.

For a random walk with , the probability of traveling a given distance after steps is given in the following table.

steps					0	1	2	3	4	5
0					1
1					0
2				0		0
3			0		0		0
4		0		0		0		0
5	0		0		0		0		0

In this table, subsequent rows are found by adding Half of each cell in a given row to each of the two cellsdiagonally below it. In fact, it is simply Pascal's Triangle padded with intervening zeros and with eachrow multiplied by an additional factor of 1/2. The Coefficients in this triangle are given by

(16)

The expectation value of the distance after

steps is therefore


			(17)

This sum can be done symbolically by separately considering the cases

Even and

Odd. First,consider Even

so that

. Then





	(18)

But this sum can be evaluated analytically as

(19)

which, when combined with

and plugged back in, gives

(20)

But the Legendre Duplication Formula gives

(21)

(22)

Now consider

Odd, so

. Then








	(23)

But the Hypergeometric Function

has the special value

(24)

(25)

Summarizing the Even and Odd solutions,

(26)

where

(27)

Written explicitly in terms of ,

(28)

The first few values of

are then

Now, examine the asymptotic behavior of . The asymptotic expansion of the Gamma Function ratio is

(29)

(Graham et al. 1994), so plugging in the expression for

gives the asymptotic series

(30)

where the top signs are taken for

Even and the bottom signs for

Odd. Therefore, for large

(31)

which is also shown in Mosteller et al. (1961, p. 14).

See also Binomial Distribution, Catalan Number, p-Good Path, Pólya's Random WalkConstants, Random Walk--2-D, Random Walk--3-D, Self-Avoiding Walk

References

Chandrasekhar, S. ``Stochastic Problems in Physics and Astronomy.'' Rev. Modern Phys. 15, 1-89, 1943. Reprinted in Noise and Stochastic Processes (Ed. N. Wax). New York: Dover, pp. 3-91, 1954.

Feller, W. Ch. 3 in An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed., rev. printing. New York: Wiley, 1968.

Gardner, M. Chs. 6-7 in Mathematical Carnival: A New Round-Up of Tantalizers and Puzzles from Scientific American. New York: Vintage Books, 1977.

Graham, R. L.; Knuth, D. E.; and Patashnik, O. Answer to problem 9.60 in Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.

Hersh, R. and Griego, R. J. ``Brownian Motion and Potential Theory.'' Sci. Amer. 220, 67-74, 1969.

Kac, M. ``Random Walk and the Theory of Brownian Motion.'' Amer. Math. Monthly 54, 369-391, 1947. Reprinted in Noise and Stochastic Processes (Ed. N. Wax). New York: Dover, pp. 295-317, 1954.

Mosteller, F.; Rourke, R. E. K.; and Thomas, G. B. Probability and Statistics. Reading, MA: Addison-Wesley, 1961.

随便看

数学辞典收录了8975条数学词条，基本涵盖了常用数学知识及数学英语单词词组的翻译及用法，是数学学习的有利工具。