I'm given this figure and I need to find transition matrix for this. Thep problem says that the robots have been programmed to traverse the maze and at each junction randomly choose which way to go. I gave it a shot but doing these kinds of problems confuse me so I was just hoping if someone could check if it is correct. Also, how would I go about finding the stead state if I'm given 15 robots at each junction?
$$ A= \begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ \end{bmatrix} $$
The way you described the problem is that the robots cannot stay in one place, but have to move each step.
If you are at step one, you have two possible paths (to $3$ and to $2$), so the robot takes each path with the equal probability of $1/2$.
At step two there are 3 paths with each the probability of $1/3$.
At step $3$ you have $4$ possible paths, that means you take each one with the probability $1/4$. But two of the paths go to $4$ so the probability of getting from $3$ to $4$ is $1/4+1/4 = 1/2$
And similarly for $4$: There are $3$ possible paths, each is taken with probability $1/3$, but two lead to the same node $3$, so the probability for getting from $4$ to $3$ is $1/3+1/3 = 2/3$.
And they move with equal probability in each of the available steps, so I'd say the transitionmatrix looks like this (writing the state vectors $x$ as row vectors $x = (x_1, \ldots ,x_4)$ and multiplying like $xA$ as it is conventionally done when working with Markov chains):
$$ A= \begin{bmatrix} 0 & 1/2&1/2& 0 \\ 1/3& 0 &1/3&1/3 \\ 1/4& 1/4& 0 &1/2\\ 0 & 1/3&2/3& 0 \\ \end{bmatrix} $$
I hope this helps=)