The simple random walk is: [x] <- [a] <->

**-> [y] with equal probabilities in each direction.**

In canonical form, the transition matrix looks like:

$

\begin{array}{c}

a \\ b \\ x \\ y

\end{array}

\left[ \begin{array}{cccc}

0 & 1/2 & 1/2 & 0 \\

1/2 & 0 & 0 & 1/2 \\

0 & 0 & 1 & 0 \\

0 & 0 & 0 & 1 \end{array} \right] =

\left[ \begin{array}{cc}

Q & R \\

0 & I \end{array} \right]

$

I never covered these in any of my classes, so all info has been from online texts. Assuming I start at node [a], I get both via simulation and online equations, that: P[x] = 2/3, P[y] = 1/3. That is, given infinite simulations, 2/3'rds of them will end in [x], 1/3 will end in [y].

So here's the problem. How long it takes before the walk is absorbed into each x & y node. I haven't found any information online regarding the expected hit time for each end-point. Given a very simple simulation (code below), it's noticed (starting from [a]) that the average number of nodes traveled until hitting [x] is 5/3, and the average to hit [y] is 8/3.

Previously, I'd simply have done a recurrence relation as follows [x] <- [a] <->

In canonical form, the transition matrix looks like:

$

\begin{array}{c}

a \\ b \\ x \\ y

\end{array}

\left[ \begin{array}{cccc}

0 & 1/2 & 1/2 & 0 \\

1/2 & 0 & 0 & 1/2 \\

0 & 0 & 1 & 0 \\

0 & 0 & 0 & 1 \end{array} \right] =

\left[ \begin{array}{cc}

Q & R \\

0 & I \end{array} \right]

$

I never covered these in any of my classes, so all info has been from online texts. Assuming I start at node [a], I get both via simulation and online equations, that: P[x] = 2/3, P[y] = 1/3. That is, given infinite simulations, 2/3'rds of them will end in [x], 1/3 will end in [y].

So here's the problem. How long it takes before the walk is absorbed into each x & y node. I haven't found any information online regarding the expected hit time for each end-point. Given a very simple simulation (code below), it's noticed (starting from [a]) that the average number of nodes traveled until hitting [x] is 5/3, and the average to hit [y] is 8/3.

Previously, I'd simply have done a recurrence relation as follows [x] <- [a] <->

**-> [y]:**

E[x to x] = 0

E[a to x] = (E[x to x]+1)/2 + (EE[x to x] = 0

E[a to x] = (E[x to x]+1)/2 + (E

**+1)/2**

EE

**= (E[a to x]+1)/2 + 0**

Yields: E[x to x] = 0, E[a to x] = 5/3, EYields: E[x to x] = 0, E[a to x] = 5/3, E

**= 4/3.**

The value for E[a to x] is correct, but EThe value for E[a to x] is correct, but E

**is not. I'm been pouring over literature & fiddling with numbers and equations for days now trying to figure it out to no avail. What am I missing here?**

Python sim, very simple.

Python sim, very simple.

Code: Select all

```
def sim4():
lst=time();
trial=0;
total_length=[0]*2;
times=[0]*2;
while True:
trial+=1;
room=0; travel=0;
while True:
if(room==0): room=choice([1,2]);
elif(room==1): room=choice([0,3]);
else: break;
travel+=1;
termroom=room-2;
total_length[termroom]+=travel;
times[termroom]+=1;
if(time()-lst>10):
lst=time();
EX,EY = [float(total_length[i])/times[i] for i in [0,1]];
PX,PY = [float(times[i])/sum(times) for i in [0,1]];
print "E[x]=%r\tE[y]=%r\tP[x]=%s\tP[y]=%s\t\t%s\t%s"%(EX,EY,PX,PY,total_length,times);
from random import choice;
sim4();
```