Taking the long way around

In order to determine the probability the guard walks more than the expected number of lengths of hallway, we must first determine the expected number of lengths of hallway. When the guard is in a corner that is not his starting corner, he can be in 3 possible states. He can either be a) at the opposite corner, b) at an adjacent corner facing the starting corner, c) at an adjacent corner facing the opposite corner. Let $A,B,C$ respectively be the expected number of lengths of hallway walked from each of these to get back to the starting corner.

We have the relations $A = 1 + B, B = 1 + \frac{1}{4}A, C = \frac{3}{4}A + 1$ . Solving this system gives $A = \frac{8}{3}, B = \frac{5}{3}, C = 3$ . When the guard arrives at the first corner, he will have orientation c, so the expected number of hallway lengths walked fom here is 3. Combined with the additional length walked to get here is a total of 4 lengths.

In order for the guard to walk more than the expected number of lengths, he must be on the opposite corner from where he started after walking 2 lengths and after walking 4 lengths. The probability he is there after walking 2 lengths is $\frac{3}{4}$ . After the third length he will have orientation b, so there is a $\frac{1}{4}$ chance that he will return to the opposite corner after this. Thus, the probability is $\frac{3}{4}\cdot \frac{1}{4} = \frac{3}{16}$ that he arrives back to where he started after walking more than the expected number of lengths of hallway. Thus, $a + b = 3 + 16 = 19$ .

First, find the expected number of steps by taking the state transition matrix to infinity. Expected steps = 4. As the question states the probability to be strictly >4, there are only 3 ways by which can there be less than 4 steps to return to the original position. 1) Pillar 1 to 2 then back to 1 2) Pillar 1 to 2, to 3, to 2, to 1 3) Pillar 1 to 2, to 3, to 4, to 1 Probability of each case can be calculated easily, and use 1 to minus off the answer to get probability of it strictly above 4 steps. Which I got 3/16.

Form relations based on probability and chances you get simultaneous equations and then solve them.

Label the vertices of the squares $A, B, C, D$ . WLOG, let $A$ be the upper-right corner and the vertices $B, C, D$ be in clockwise order, i.e. $B$ is the upper-left corner and etc... Let the guard start at $A$ . Denote $E_{K}$ as the expected number of hallways from vertex $K$ the guard moves to get to the starting position. Note that $E = E_{B}$ . Now we can form equations related to $E_{B}, E_{C}, E_{D}$ to find them.

Note that the probability to get $2$ heads is $\frac{1}{4}$ . Note that $E_{B} = \frac{1}{4}(1) + \frac{3}{4}(E_{C} + 1)$ since if the guard gets $2$ heads, then he just need to walk for $1$ hallway, since he will go back to $A$ in one move. Otherwise, he will go $E_{C} + 1$ hallways since he walks $1$ hallway to get to $C$ and he will walk $E_{C}$ hallways to get back to $A$ . Similarly, we get $E_{C} = \frac{1}{4}(E_{B} + 1) + \frac{3}{4}(E_{D} + 1)$ and $E_{D} = \frac{1}{4}(E_{C} + 1) + \frac{3}{4}(1)$ Solving these $3$ equations, we get $E_{B} = \frac{17}{5}, E_{C} = \frac{16}{5}, E_{D} = \frac{9}{5}$ and thus $E = \frac{17}{5} = 3.4$ .

Now, we just need to $p$ , which is the probability that the guard walk strictly greater than $3.4$ hallways, i.e. at least $4$ hallways. The probability that the guard walks for $1$ hallway is $\frac{1}{4}$ (getting two heads). It is impossible for the guard to walk $2$ hallways. And the probability that the guard walks for $3$ hallways is $\frac{3}{4} \cdot \frac{3}{4} \cdot \frac{3}{4} + \frac{3}{4} \cdot \frac{1}{4} \cdot \frac{3}{4} = \frac{9}{16}$ . (B -> C -> D -> A and B -> C -> B (two heads) -> A). It is trivial to check that these are the only possibilities.

So, $p = 1 - \frac{1}{4} - \frac{9}{16} = \frac{3}{16}$ , so $a + b = \boxed{19}$ .

Everytime he reaches a corner there are 4 outcomes.. so 1/4 of the time he goes back and 3/4 of the time he goes ahead right...

in total there are three other corners aside from the starting corner... i think this is the tricky part and i may be mistaken here... for E.. the expected number is the number where he does not have to turn back at all.. the probability of this happening is (3/4)^3 or(27/64) since there are three independent events 3/4 being the chance of going ahead in each event.. in conclusion the expected number for E is 4 lengths of hallways all in all..

there are other two cases where he only takes 4 lengths... that being turning back on the first corner and turning back on the second corner... in turning back in the first corner the probability of that is 1/4 and turning back the second corner and reaching start is (3/4)^2 *(1/4) which is 9/64

adding all three we get 27/64 +16/64(or 1/4)+ (9/64) = 52/64

on the other hand, the other situations will get a higher value for E so p=1-(52/64) so p=12/64. simplify 12/64 to 3/16 so a+b is 19

The shortest possible path has length 2 (walking 1 hallway clockwise and 1 hallway anticlockwise) and the probability is $\frac {1}{4}$ (the chance of two heads on the first corner).

The second shortest path has length 4 and the probability is $\frac {3}{4}^3 = \frac {27}{64}$ (the probability of walking around, passing all 4 hallways) plus $\frac{3}{4} \cdot \frac{1}{4} \cdot \frac{3}{4} = \frac{9}{64}$ (the probability of turning around and retracing your steps after 2 hallways).

Since the probability of walking 2 hallways is less than $\frac{1}{2}$ and the probability of walking 4 hallways is significantly more than $\frac{1}{2}$ , the expected number of hallways (the weighted average) can be found to be between 2 and 3. Since the number of hallways must be an integer, the probability of walking 6 or more hallways is the solution to this problem.

We found that the probability of walking 2 or 4 hallways is $\frac{1}{4} + \frac{9}{64} + \frac{27}{64} = \frac{13}{16}$ . This means that the probability of walking strictly more than the expected number of hallways is $1 - \frac{13}{16} = \frac{3}{16}$ .