Sheldon Ross 10: Example 2.53

Sheldon Ross 10 Example 2.53(loop)_2-01.jpg

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 Xn 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} = 1/2 where i + 1 ≡ 0

When i = m, and i − 1 ≡ 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 ith node can be accessed from either (i-1)th node or (i+1)th
  • Then, the probability that (i-1)this 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 the number of the nodes – 1 ( the minus one excluding itself! )

Given that we understand how the probability that any one of them could be last is equal to 1m, 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


Code: The code used for the simulation is shown below. It is rather in a very condensed form and might take a while to understand depending on your expertise with Mathematica. Note that the pairs in red is just a warning. That did not cause any issues while using the code


End of the post


.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.