The goal of this project is to find the probability that a random subject will return to his starting place some point during a drunken walk in a generalized number of dimensions. We also explore drunken walks taking place in cylindrical space as well as on a torus.
In[]:=
(*CreatingtheDrunkenWalk*)
In[]:=
drunkenWalk[n_,k_]:=Module[{steps},​​steps=Join[IdentityMatrix[k],-IdentityMatrix[k]];​​Accumulate[Prepend[RandomChoice[steps,n],ConstantArray[0,k]]]​​]
In[]:=
drunkenWalkEnd[n_,k_]:=drunkenWalk[n,k][[-1]]
In[]:=
(*​​Checkingifthesubjecthasreturnedhomeatanypointuptosomen.​​Wedon'tcheckforanynbecauseofcomputationaltimeout,howeverifonemustperformoperationsneedinganyn,onemaysimplytakethelimit.​​Oftheform{True/False,j,{RandomWalksequenceexludingthe{0,0}term}}wherejisnonemptywhenthesubjectsreturnstothestartatstepj.​​*)
In[]:=
returnHomeQ[n_,k_]:={If[MemberQ[Delete[drunkenWalk[n,k],1],ConstantArray[0,k]]True,True,False],FirstPosition[Delete[drunkenWalk[n,k],1],ConstantArray[0,k]],Delete[drunkenWalk[n,k],1]}
In[]:=
returnHomeQ[10,2]
Out[]=
{False,{2},{{-1,0},{-1,1},{-1,0},{-1,-1},{-1,0},{-1,-1},{-2,-1},{-1,-1},{-1,0},{0,0}}}
In[]:=
(*Extractingthenumberofstepsittakestoreturnhomeandfindingtheaveragenumberofsteps(wechoosen=100foracuraccyandcomputation)*)​​returnHomeValue[n_,k_]:=Module[{v},​​v=returnHomeQ[n,k]〚2〛;​​If[v===Missing["NotFound"],0,v]​​]
In[]:=
avgNumOfSteps[k_]:=0.01*Sum[returnHomeValue[100,k],{i,100}]
In[]:=
(*Wemaynowgraphtheaveragenumberofstepsforeachk*)
In[]:=
BarChart[Table[avgNumOfSteps[m],{m,1,10}]]
Out[]=
One thing to notice is that when the subject never returns back to the start, the value of returnHomeValue[] is
0
, thus if a subject never returns home it will pull the value of avgNumOfSteps[] down (in that subjects respective dimension), thus for small outputs of avgNumOfSteps[] we can guess that subject has gotten lost several times. We may increase the accuracy of avgNumOfSteps[] by simply increasing
n
, and one may guess that by bringing
n
up, we also bring up the value of avgNumOfSteps[], however as we can see below (we change the accuracy to
n=200
and recreate out bar chart) this is not the case,
In[]:=
avgNumOfSteps[k_]:=0.01*Sum[returnHomeValue[200,k],{i,200}]
In[]:=
BarChart[Table[avgNumOfSteps[m],{m,1,10}]]
Out[]=
For one final reassurance, we may increase the value of
n
to
1000
and also consider up to
k=20
:
In[]:=
avgNumOfSteps[k_]:=0.01*Sum[returnHomeValue[1000,k],{i,200}]
In[]:=
BarChart[Table[avgNumOfSteps[m],{m,1,20}]]
Out[]=
In[]:=
avgNumOfSteps[k_]:=0.01*Sum[returnHomeValue[100,k],{i,200}]
One may notice a very logical trend, that being: As
k
grows large, the subject gets lost more and more often (This will be explained later). However, something that seems very illogical is that the subject seems to get lost often for
k=1
. If we were to view the random walk through the eyes of the subject, we would start by either moving towards
-1
or
1
(left or right), if we move to
-1
, then we will never be able to get to
1
because we would end up at home before we could reach
1
, and similarly if we were to move to
1
first. Thus we can just assume without loss of generality that the subject moves to
1
and we can ignore
-1,-2,...
At this point, there is a 50% chance that the subject returns home, if the subject moves away (onto 2) from his home, there is now a 25% percent chance that the subject will return back home, and so on. Thus we may form a very crude statement: If the subject does not return home after the second step for
k=1
, he will most likely get lost. We now my look at the chance that the subject will return home in a more general situation,
In[]:=
chanceOfReturn[k_]:=Module{v,u},​​v=Table[returnHomeValue[100,k],{i,0,100}];​​N
Length[Select[Flatten[v],#1>0&]]
Length[Flatten[v]]
​​
In[]:=
BarChart[Table[chanceOfReturn[k],{k,1,5}]]
Out[]=
We can see a much more logical trend in the percentage of the times that the subject will return to his home for a given
k
, we can notice that for
k=1
he returns home almost all of the time, thus we may revisit our guess at the smaller spike in the average number of steps required to get back home, and one can easily come to the conclusion that it was not being skewed by 0s and instead just being skewed by small numbers of steps. The biggest jumps are from
k=1
to
k=2
which is expected, but then there is a very large jump from
k=2
to
k=3
. One way that we can explain this jump is that for
k=2
there is always two lines that you need to travel upon to reach
{0,0}
and
4
different possible directions that you can go, but in the
k=3
case there are
3
lines that you must travel on to reach
{0,0}
but there is now
6
directions, and for
k=4
there is
4
lines but
8
different directions you can move. If we put a restriction on our space that grows with every step, (i.e. putting walls around the player that grow with every step, however we may put the following requirement on the walls as to gain some information about the space: If we label the walls
w
1
,
w
2
,
w
3
,...,
w
2k
, when the subject steps towards wall
w
n
we increase the distance to
w
n
from the origin by one, and we fill in the gaps that are created.) the subject will never reach the walls, however it will stay some distance from each, if we commutative total of each distance for
k=2
and
3
, we will see that in
2
the distance increases over time, and this is because the subject may get close to a wall however it will eventually move towards that wall increasing the distance from it to
{0,0}
and then move away increasing the total distance from the subject to the walls, however in the
k=3
case, the subject will again eventually move near a wall however the subject will have a tendency to stay closer to the walls because there is more of them to be near, thus the subject will keep the distance to the walls small and thus never move back to the origin (same goes for the
k=4,5,..
. cases). A good way to think about this is that in the
k=3,4,....
cases there is too much space and the subject gets lost every time. We now may look at a much more general drunken walk:
In[]:=
(*ModifyingtheoriginaldefinitionsofdrunkenWalkandthesubsequentfunctionstotakeinalistofpositiveintegersstepSizesthatspecifythepossiblestepsizesthatthesubjectcouldtake,onemaysetstepSizestobe{1}astoregainalltheoriginalfunctions.*)​​genDrunkenWalk[n_,k_,stepSizes_List]:=Module[{steps,path},​​steps=Flatten[Table[Join[sIdentityMatrix[k],-sIdentityMatrix[k]],{s,stepSizes}],1];Accumulate[Prepend[RandomChoice[steps,n],ConstantArray[0,k]]]]
In[]:=
genDrunkenWalkEnd[n_,k_,stepSizes_List]:=genDrunkenWalk[n,k,stepSizes][[-1]]​​genReturnHomeQ[n_,k_,stepSizes_List]:={If[MemberQ[Delete[genDrunkenWalk[n,k,stepSizes],1],ConstantArray[0,k]]True,True,False],FirstPosition[Delete[genDrunkenWalk[n,k,stepSizes],1],ConstantArray[0,k]],Delete[genDrunkenWalk[n,k,stepSizes],1]}​​genReturnHomeValue[n_,k_,stepSizes_List]:=Module[{v},v=genReturnHomeQ[n,k,stepSizes]〚2〛;If[v===Missing["NotFound"],0,v]]​​avgNumOfSteps[k_,stepSizes_List]:=0.01*Sum[genReturnHomeValue[100,k,stepSizes],{i,100}]
In[]:=
(*Exampleevaluations*)
In[]:=
genDrunkenWalk[15,3,{1,2,3}]​​genDrunkenWalkEnd[30,4,{1,2,3,4,5}]​​genReturnHomeQ[20,2,{1,2}]​​genReturnHomeValue[15,2,{1,2,3}]​​avgNumOfSteps[3,{1,2,3}]
Out[]=
{{0,0,0},{0,0,-1},{0,-1,-1},{0,-1,-4},{0,-1,-3},{1,-1,-3},{-2,-1,-3},{-2,-1,-4},{-2,-1,-7},{-2,-4,-7},{-2,-4,-10},{-2,-4,-12},{-2,-4,-15},{-3,-4,-15},{-3,-1,-15},{-3,-1,-18}}
Out[]=
{-7,-22,6,5}
Out[]=
{False,Missing[NotFound],{{0,-1},{0,-2},{0,-1},{-2,-1},{-2,-2},{0,-2},{2,-2},{3,-2},{4,-2},{4,-4},{4,-2},{4,-1},{5,-1},{5,-2},{5,-4},{3,-4},{4,-4},{4,-2},{3,-2},{5,-2}}}
Out[]=
0
Out[]=
{0.93}
We may again look at the graphs of the chance that the subject returns home for some set of step sizes,
In[]:=
genChanceOfReturn[k_,stepSizes_]:=Module{v,u},​​v=Table[genReturnHomeValue[100,k,stepSizes],{i,0,100}];​​N
Length[Select[Flatten[v],#1>0&]]
Length[Flatten[v]]

In[]:=
Table[Labeled[BarChart[Table[genChanceOfReturn[k,Range[j]],{k,1,5}]],Row[{"stepSizes = ",Range[j]}],Top],{j,1,5}]
Out[]=

stepSizes = {1}
,
stepSizes = {1,2}
,
stepSizes = {1,2,3}
,
stepSizes = {1,2,3,4}
,
stepSizes = {1,2,3,4,5}

We can then again look at all the other statistics that we have been using to analyze the other random walks,
We again see the same logical trend with the radius.