Targil 2

1. Exact Enumeration The goal of this part was to write a program that enumerates NW(x,N),
the total number of random walks of N steps that reach the point x, for all x for N=4,5,6,7 and 8. 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:
the answers to the question
Here are some insights:
2. Simulation 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:

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.
example graph