1. Exact Enumeration
The goal of this part was to write a program that enumerates
the total number of random walks of N
steps that reach the point
for all x
I wrote a general program for all N and can be downloaded here
The enumeration is simply the recursion: NW(x,N)=NW(x-1,N-1)+NW(x+1,N-1),
according to the considerations discussed in class.
The main code is 'Targil2_Q1.m' - the first parts allows to calculate NW(x,N) for any x,N, and the second part creates the table shown below.
For the requested N values, the results are pictured in the following table:
Here are some insights:
- Note that for x=+/-N, NW=1, as expected.
- For odd N values only even x's are possible and for even N values only odd x's are possible.
- The table clearly shows the relation with Pascal's triangle.
I used the programs rwalk1.f and cplot.f to draw graphs of PN(x)
, the probability that after N steps a walker has net displacement x, for N=8,16,32 and 64. I experimented with different seeds (all odd and large numbers) and following are my conclusions:
- The sigma rises with the number of steps. This is expected since the probability of going left or right is the same, so if we allow more steps, we actually allow the walker to get farther away from zero.
- I also noticed that for a larger seed, the graph is more likely centered around zero. This is also somewhat expected, since a larger seed means larger randomness so the chances for ending up on a positive and negative x is more similar.
- In general, increasing N and the seed produces a graph similar to Gaussian, again for obvious reasons.
Following is an example for a graph generated by cfplot for a seed of 13579861 and N=64. Note that the graph is not completely symmetric around 0, as one would expect, since the code is only pseudo random and the number of trials is finite. Nevertheless, the probability of reaching |x|>20 is zero since the chances of going 20 times more to the right than to the left or vice versa is very slim.