We will construct all possible valid E-W sequences. Let s be any one of the valid E-W sequences. Firstly, Gracie walks one
block east from his house initially, so the first term of s must be a E. Secondly, he can not return to his house before his
8th step of block-walking, so the total number of Es in any subsequence of s with less than 8 terms must be greater than that
of Ws. Thirdly, we are only interested in s where Gracie returns home in exactly 8 steps, so the number of Es and Ws of s
must both be 4. By these three observations, we can construct the following 5 valid E-W sequences:
Every choice of E or W after the first term in each valid E-W sequence occurs with a probability of 1/2, so the probability
of occurrence in each valid E-W sequence is (1/2)^7 = 1/128. With 5 valid E-W sequences, the desired probability is 5/128.
Let p(x, s) denotes the probability that Gracie is at x on the sth step. We are given that p(0, 0) = p(1, 1) = 0, and we are
to find p(0, 8). When x >= 2, if Gracie is at x on the (s+1)th step, then there is a chance of 1/2 that he came from x-1, and
there is another chance of 1/2 that he came from x+1, from the sth step. When Gracie is at x = 0 or 1 on the (s+1)th step,
then he could only come from x+1 = 1 or 2 on the sth step, respectively, with a chance of 1/2. With this definition of
p(x, s), we can set up the a recursion as follows:
p(x, s+1) = p(x-1, s)/2+p(x+1, s)/2 if x >= 2;
p(1, s+1) = p(2, s)/2;
p(0, s+1) = p(1, s)/2;
p(0, 0) = 1;
p(0, s) = 0 if s <> 0;
p(1, 1) = 1;
p(1, s) = 0 if s <> 1.
Using this recursion, we can build up the the table above. Reading off from the table, the desired probability is
p(8, 0) = 5/128.