Non User
Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z	Business Non User Industries Finance Tax

Home > Random walk

A random walk is a simple stochastic process.

A random walk is sometimes called a "drunkard's walk". Drunkard's Walk is also the name of a 1960 science fiction novel by Frederik Pohl.

1 Properties

The simplest random walk is a path constructed according to the following rules:

• There is a starting point.
• The distance from one point in the path to the next is a constant.
• The direction from one point in the path to the next is chosen at random, and no direction is more probable than another.

The average straight-line distance between start and finish points of a random walk of n steps is on the order of √n. In fact, if "average" is understood in the sense of root-mean-square, then the average distance after n steps is exactly times the step length.

Suppose we draw a line some distance from the origin of the walk. How many times will the random walk cross the line? The following, perhaps surprising, theorem is the answer: for any random walk, every point in the domain will be crossed an infinite number of times almost surely. This problem has many names: the level-crossing problem, the recurrance problem or the gambler's ruin problem. The source of the last name is as follows: if you are a gambler with a finite amount of money playing a fair game against a bank with an infinite amount of money, you will surely lose. The amount of money you have will perform a random walk but it will, almost surely, reach at some time 0, and the game would be over.

2 Example

The graph of eight random walks, each starting at zero, are shown here for 100 timesteps. At each time step, they go either one step up or down. As one can see, while they remain clustered around their common origin (the horizontal axis), their average distance to the origin does indeed increase, but more slowly than linearly.

3 Higher dimensions

Imagine now a drunkard walking around in the city. The city is infinite and completely ordered, and at every corner he chooses one of the four possible routes (including the one he came from) with equal probability. Formally, this is a random walk on the set of all points in the plane with integer coordinatesGeometry See Cartesian coordinate system or Coordinates (elementary mathematics) for a more elementary introduction to this topic In mathematics as applied to geometry, physics or engineering, a coordinate system is a system for assigning a tuple of scala. Will the drunkard ever get back to his home from the bar? It turns out that he will, almost surely. This is the high dimensional equivalent of the level crossing problem discussed above. However, the similarity stops here. In dimensions 3 and above, this no longer holds. In other words, a drunk bird might forever wander around, never finding its nest. The formal terms to describe this phenomenon is that random walk in dimensions 1 and 2 is recurrent while in dimension 3 and above it is transient. This was proved by PólyaGeorge Polya ( December 13, 1887 September 7, 1985, in Hungarian Polya Gyorgy was an American mathematician of Hungarian origin. He was born in Budapest, Hungary and died in Palo Alto, USA. He worked on a great variety of mathematical topics, including se in 1921Events January 2 The first religious radio broadcast ( KDKA AM in Pittsburgh, Pennsylvania) January 2 Spanish liner Santa Isabel sinks off Villa Garcia 244 dead January 2 DeYoung Museum in Golden Gate Park San Francisco opens. January 20 Republic of Turke.

The trajectory of a random walk is the collection of sites it visited, considered as a set with disregard to when the walk arrived at the point. In 1 dimension, the trajectory is simply all points between the minimum height the walk achieved and the maximum (both are, on average, on the order of √n). In higher dimensions the set has interesting geometric properties. In fact, one gets a discrete fractalA fractal is a geometric object which is "broken up" in a radical way. The term fractal was coined in 1975 by Benoit Mandelbrot, from the Latin fractus or "broken", in order to call attention to such objects. They are in a number of major aspects differen, that is a set which exhibits stochastic self-similarityA self-similar object is exactly or approximately similar to a part of itself. A curve is said to be self-similar if, for every piece of the curve, there is a smaller piece that is similar to it. For instance, a side of the Koch snowflake is self-similar; on large scales, but on small scales one can observe "jugginess" resulting from the grid on which the walk is performed. The two books of Lawler referenced below are a good source on this topic.

Politics	Business	Finance

Topics: Random Walk Motion Brownian Walks Point Graph Example...

---

Random accessIn computer science, random access is the ability to access a random element of a group in equal time. The opposite is sequential access, where a remote element takes longer time to access. A typical illustration of this distinction is the ancient scroll Random variableA random variable can be thought of as the numeric result of operating a non-deterministic mechanism or performing a non-deterministic experiment to generate a random result. For example, rolling a dice and recording the outcome yields a random variable w Random Access MemoryRandom Access Memory or RAM is a type of computer storage whose contents can be accessed in any order. This is in contrast to sequential memory devices such as magnetic tapes, discs and drums, in which the mechanical movement of the storage medium forces RandomizerIn telecommunication, the term randomizer has the following meanings: 1. A device used to invert the sense of pseudorandomly selected bits of a bit stream to avoid long sequences of bits of the same sense. Note: The same selection pattern must be used on Random numberIn statistics a random number is a single observation (outcome) of a specified random variable. Where no distribution is specified, the continuous uniform distribution on the interval [0,1) is usually, but not always, intended. In an informal sense, there RandomnessIn ordinary language, the word random is used to express apparent lack of purpose or cause. This suggests that no matter what the cause of something, its nature is not only unknown but the consequences of its operation are also unknown. In most technical Random sequence Randomization Random Harvest Random Lake, Wisconsin Random optimization Randomized controlled trial Random House Random walk Random walk Monte Carlo