1. What are Random

Walks?

1.1

A Random Walk

A random walk is a

stochastic process by which randomly-moving objects wander away from where they

started. An example of a random walk is the random walk on the integer number

line, which starts at 0 and at each step moves +1 or ?1 with equal probability 17.

1.2 Variables that govern a random walk 13, 14, 15

·

Uniformity:

If a set of random numbers between 0 and 6 is generated, the first number in

the sequence to appear is equally likely to be 0, 1, 2, . . . ,6. Additionally,

any number i in the sequence has the

equal possibility to be 0, 1, 2, . . . ,6. The average of the numbers should be

3.5.

·

Independence:

The values must be independent of each other. If it becomes possible to predict

a value in the sequence, based on the previous value, then the process is not

random. Hence, the probability of observing each value is not dependent upon

previous values.

·

Summation:

Sum of two consecutive numbers has the equal possibility to be even or odd.

·

Duplication:

When a thousand numbers a generated randomly, it is possible that some will be

duplicated. If 1,000 numbers are randomly generated, some will be duplicated.

Throwing a fair

dice with 1, 2, 3, 4, 5 or a 6 on its top face resembles a random walk. Each

throw has the probability of 1/6 of generating any of the six numbers. Again,

the throw is independent of each other and the result of one throw does not

have any impact of the next throw

regardless of how many elements have already been produced. Therefore, the

unbiased “fair” dice is thus the perfect example of generating random number, since the 1 to 6 will be

distributed randomly.

1.3 Effect of Number of Walks on Simulation 18

The effect of the

number of walk on the simulation result can be described by coin flipping game.

If it is head, then move +1 and if tail

move -1. So, after one flip, there is ½ probability to be on +1 & -1. After

two flips, there is 1/4 probability to be on +2 & -2 and ½ probability to

be on 0. Again, after three flips, there is 1/8 probability to be on +3 &

-3, 3/8 probability to be on +1 & -1and ½ probability to be on 0. So, it is

observed that it mostly hovers around the middle i.e. 0. As the coin is flipped

longer the more it spreads out. So, the probability of random walk of being in

a specific position starts to create a bell curve.

Fig 1: Number Line

1.4

Algorithm for the Dice Problem

1.

Initialize

variable: for storing the count of 5; assign number of walks (toss of dice)

2.

Repeat

simulation of random walk in the form of dice tossing 1000 times

3.

Initialize

a random number generator with numbers from 1 to six and store them

4.

If

the face of the dice after tossing is equal to 5, collect the count.

5.

Find

the probability of by dividing the number of counts by the tossing number

6.

Plot

the probability distribution of getting 5 i.e. Probability vs. Toss

7.

Compute

and print the estimated probability

1.5

Results of Fair Dice Problem

Probability for 1000 random walks = 0.171

Theoretical probability = 0.167

1.6 Discussion

The plot of the

probability as a function of a number of

‘walks walked’ is added. The plot shows that the probability is high when dice

throwing is started. This is because of getting 5s near the beginning. To get the probability, the number of 5 got is divided by the number

thrown, So, the theoretical probability is 1/6 for a fair dice. But for random

walk initially, the number of times

thrown is little compared to the number of times 5 shows. So, the probability

distribution curve shows an elevation. As the number of random walks increases it resemble theoretical result which

is evident from the above plot.

2.

Few applications

of random walks

2.1 Simulation

Simulation

is defined as the replication of the real-world operation over time 1. To

simulate something a model needs to be developed which constitutes the basic characteristics

and functions of the operation. The model represents the system itself, whereas

the simulation represents the operation of the system over time 2. Models can

be both deterministic and stochastic.

2.2 Deterministic Model

A

deterministic model is one that has no stochastic element. A process is

deterministic if its future is completely determined by its present and past.

The models are mostly described by differential equations in this case.

Different numerical methods are implemented to solve the equations: finite

difference, path simulation 3.

2.3 Stochastic Model

A

stochastic model represents a situation where uncertainty is present. In other

words, it’s a model for a process that has randomness. In this model unique

input leads to a different output for

each model run. Because of the randomness of the components, each simulation gives only one result 5.

2.4 When Random Walk Simulation is

Preferred?

A

random walk is a stochastic or random process, that defines a path that

consists of a series of random steps on a mathematical space 4. A random walk

process can’t be solved analytically. A random walk model can be simulated by

generating a random number to execute trial. Such a simulation is called ‘Monte Carlo Method’. Deterministic simulation is one kind of random

walk simulation.

In

the deterministic model, there is no

random element and simulation can be done just once. A random walk model can

handle the uncertainty in the inputs built into it. Therefore, random walk

model should be used if there are uncertainties in the inputs and the process

is not fully known 5.

With

just a few cases, the deterministic analysis

makes it difficult to see which variables impact the outcome the most. In Monte

Carlo simulation, it’s easy to see which inputs had the biggest effect on

bottom-line results.

Again,

in deterministic models, modeling different combinations of values for

different inputs to see the effects of truly different scenarios is very

difficult. Using Monte Carlo simulation, analysts can observe clearly which

inputs had which values together when certain outcomes occurred. This is

invaluable for pursuing further analysis 6.

2.5 Advantages of Monte Carlo

Simulation 6, 7

·

The model is can be flexibly used

for probability distributions

·

Models can be developed for

correlations and other relations

·

Again, independent relationships

can be established between input variables.

·

The behavior of and changes to the

model can be investigated with great ease and speed.

·

The level of mathematics required

is quite basic

2.6 Disadvantages of Monte Carlo

Simulation 6 8

·

Typically, a computer is required

·

Sometimes, calculations can be time-consuming than analytical models

·

Solutions are approximate but not

exact and depend on the number of repeated runs used to produce the output

statistics.

·

There are no limits on the error of

the computed result.