Simple solution to random walk

Question

The final score of a football match was 4:3 in favour of the home team. How many ways could the result have gone if there was a period of the match when the away team was leading? I have learnt of a formula counting this in a probability theory course. The point is that the number of random walks of length $2n$ reaching $2k$ while also visiting $-1$ at least once is the same as the number of random walks of length $2n$ reaching $2k+2$. Either way, I have to explain this exercise at an 8th grader level, so there must be an easier solution I can provide my student? Any ideas?

Edit: The method I meantion uses the fact that $\lvert S_{n,k} \rvert $ (the number of walks of $n$ steps and ending in $k$) is $ n \choose \frac{n+k}{2}$ because we have $\frac{n+k}{2}$ number of $+1$s and $\frac{n-k}{2}$ number of $-1$s because $1*\frac{n+k}{2}-1*\frac{n-k}{2}=k$. We then use a simple argument for showing that the number of random walks of length $2n$ reaching $2k$ while also visiting $-1$ at least once is the same as the number of random walks of length $2n$ reaching $2k+2$.

Edit 2: See accepted answer, beautifully put

Answer 1

One way to solve this problem is to represent the possible courses of the match by paths through a directed graph. Each vertex of the graph represents a possible score $\ (h,a)\ $ that might have occurred during the match, with $\ h\ $ being a score for the home team, $\ a\ $ being a score for the away team, $\ 0\le h\le4\ $ and $\ 0\le a\le3\ .$ The graph contains a directed edge from the vertex representing the score $\ \big(h_1,a_1\big)\ $ to that representing the score $\ \big(h_2,a_2\big)\ $ if and only the latter score is one that could immediately follow the former during the match—that is, if and only if either $\ h_2=h_1+1\ $ and $\ a_2=a_1\ $ or $\ h_2=h_1\ $ and $\ a_2=a_1+1\ .$ Here's a diagram of such a graph:

The total number of ways the game could have occurred is the number of directed paths from the initial vertex, $\ (0,0)\ ,$ to the final vertex, $\ (4,3)\ .$ Calculating this is very simple. The total number of directed paths from the initial vertex to any other vertex is the sum over all immediate predecessors of the latter vertex of the number of directed paths to those predecessors, where we artificially consider the number of directed paths to the initial vertex to be equal to $1$. Starting with the immediate successors of the initial vertex we can successively label each vertex of the graph with the number of directed paths to that vertex once all its immediate predecessors have been labelled. The result of this procedure is illustrated in the following diagram, from which we see that there are $35$ possible ways the game could have occurred.

The red vertices in the graph represent situations where the away team is in the lead, and what you actually want is the total number of directed paths from the initial to the final vertex that visit at least one of the red vertices. The easiest way to calculate this is to instead calculate the total number of directed paths that never visit a red vertex and subtract it from the total number of paths already calculated. The number of directed paths that never visit a red vertex is just the total number of directed paths that visit only black vertices, and this can be calculated in the same way as was done for the total number of paths, but this time ignoring the red vertices. The result is illustrated in the following diagram, from which we see that there are a total of $14$ directed paths from the initial vertex to the final vertex that never visit any of the red vertices.

Thus, the number of ways the game could have occurred if the away team was in the lead at some stage is $\ 35-14=21\ .$

Answer 2

With the $X$-axis representing score of the home team and the $Y$-axis that of the away team. write down scores as

$0-3\mid 1-3 \mid 2-3 \mid 3-3 \mid 4-3$
$0-2\mid 1-2 \mid 2-2 \mid 3-2 \mid 4-2$
$0-1\mid 1-1 \mid 2-1 \mid 3-1 \mid 4-1$
$0-0 \mid 1-0 \mid 2-0 \mid 3-0 \mid 4-0$

You can now trace all "valid" paths, or use combinations if the student has been taught that

---

$\textbf{Added Material}$

I have added a solution using combinations that should be accessible to an $8$th grade

• The away team can start on a leading path only at goal $1$,$3$, or $5$, by a win, and to understand more easily, a $W$ here will represent a win for the away team

• A win at $1$ gives $\binom62=15$ ways for the remaining part

• A leading pattern win at goal $3$ must be preceded by $LW$, with permutations of $WLLL$ left, thus $\cdot\binom41 = 4$ ways

• Leading pattern win at goal $5$ must be preceded by $LWLW/LLWW$ followed by $LL$, thus $2\cdot1 =2$ ways

• Finally adding up, ans $= 15+4+2 = 21$