Probability | Graphs | Last Visited Node

Question

Consider a particle that moves along a set of \(m + 1\) nodes, labeled \(0, 1, . . . ,m\), that are arranged around a circle. At each step the particle is equally likely to move one position in either the clockwise or counterclockwise direction. That is, if \(X_{n}\) is the position of the particle after its nth step then \[P\{Xn+1 = i + 1|Xn = i\} = P\{Xn+1 = i − 1|Xn = i\} = \frac{1}{2} : i + 1 \equiv 0\] When \(i = m\), and \(i − 1 \equiv m\) when \(i = 0\). Suppose now that the particle starts at 0 and continues to move around according to the preceding rules until all the nodes \(1, 2, ..., m\) have been visited. What is the probability that node \(i: i = 1, ..., m\) is the last one visited?

Solution

There is a rather intuitive way to understand this problem.

• Let us say that you are interested in the probability that \((i)^{th}\) position (or rather, the probability that is \((i)^{th}\) the last node visited)
• This means that the \((i)^{th}\) node can be accessed from either \((i-1)^{th}\) node or \((i+1)^{th}\)
• Then, the probability that \((i-1)^{th}\) is visited is dependent on whether the current state is in \((i)^{th}\) state or \((i-2)^{th}\) state
• Since this is a loop that closes on itself, starting at any point would mean that that that sequence would ultimately lead to itself
• This means that the probability that any node is the last one is equal to \(\frac{1}{(n-1)}\)
  
• \(n-1\) as in excluding itself!

Given that we understand how the probability that any one of them could be last is equal to, it is time for some simulations 😀

Simulations

Given below are four simulations of the scenarios. All of them have been run for 1000 steps and you can see the dynamic state of the system rapidly fluctuating as it tries to make a roundabout

\(m + 1 = 15\)

\(m + 1 = 20\)

\(m + 1 = 25\)

\(m + 1 = 30\)

ClearAll[circumventer, circleSequence, particleInCircle, particleInCircleExport];

circumventer[n_, size_: 10] := Mod[Abs[size + n], size]

circleSequence[n_: 10, radius_: 10, activeIn_List] :=
    Module[{active = activeIn + 1},
        Table[{
            If[active[[2]] == r, {Opacity[1.0], Green, Disk[{radius Sin[2 r \[Pi]/n], radius Cos[2 r \[Pi]/n]}]},
            If[active[[1]] == r, {Opacity[0.2], Green, Disk[{radius Sin[2 r \[Pi]/n], radius Cos[2 r \[Pi]/n]}]},
            {Opacity[1.0], Green,Circle[{radius Sin[2 r \[Pi]/n], radius Cos[2 r \[Pi]/n]}]}]]}, {r, 1, n}]
            ~Join~
            {Lighter@Blue, Arrow[{radius {Sin[2 active[[1]] \[Pi]/n], Cos[2 active[[1]] \[Pi]/n]}, radius {Sin[2 active[[2]] \[Pi]/n],
        Cos[2 active[[2]] \[Pi]/n]}}]}
  ]

particleInCircle[\[Gamma]_: 10, sample_: 1000] :=
    Module[{preverse = {0}, simulation, pairs}, Table[AppendTo[preverse, RandomChoice[{-1, 1}]], sample];
    simulation = circumventer[#, \[Gamma]] & /@ Accumulate[preverse];
    pairs = Transpose[{Drop[simulation, -1], Rest[simulation]}];
    Manipulate[
        Graphics[circleSequence[\[Gamma], 12, pairs[[r]]], ImageSize -> 350], {r, 1, Length@pairs, 1}]]

particleInCircleExport[\[Gamma]_: 10, sample_: 1000] :=
    Module[{preverse = {0}, simulation, pairs}, Table[AppendTo[preverse, RandomChoice[{-1, 1}]], sample];
    simulation = circumventer[#, \[Gamma]] & /@ Accumulate[preverse];
    pairs = Transpose[{Drop[simulation, -1], Rest[simulation]}];
    Table[Graphics[circleSequence[\[Gamma], 12, pairs[[r]]], PlotRange -> {{-15, 15}, {-15, 15}}], {r, 1, Length@pairs, 1}]]


Export[StringReplace[NotebookFileName[], ".nb" -> "_animation_" <> ToString[#[[1]]] <> "_" <> ToString[#[[2]]] <> ".gif"],
    particleInCircleExport[#[[1]], #[[2]]], ImageSize -> 400, ImageResolution -> 300, "DisplaDurations" -> 0.2] & /@
        {{15, 1000}, {20, 1000}, {25, 1000}, {30, 1000}}