# Random Walk III

Alignments to Content Standards: S-CP.B.9

Imagine Scott stood at zero on a life-sized number line. His friend flipped a coin $6$ times. When the coin came up heads, he moved one unit to the right. When the coin came up tails, he moved one unit to the left. After each flip of the coin, Scott's friend recorded his position on the number line. Let $f$ assign to the whole number $n$, when $1 \leq n \leq 6$, Scott's position on the number line after the $n^{\rm th}$ coin flip.

1. How many different outcomes are there for the sequence of $6$ coin tosses?
2. Calculate the probability, before the coin flips have begun, that $f(6) = 0$, $f(6) =1$, and $f(6)= 6$.
3. Make a bar graph showing the frequency of the different outcomes for this random walk.
4. Which number is Scott most likely to land on after the six coin flips? Why?

## IM Commentary

This task is part of a progression, starting with Random Walk and Random Walk II which stressed the function aspect of this situation, transitioning to the probability and statistics side.

The task provides a context to calculate discrete probabilities and represent them on a bar graph. It could also be used to create a class activity where students gather, represent, and analyze data, running simulations of the random walk and recording and then displaying their results.

## Solutions

Solution: 1.

1. If we denote by $H$ an outcome of heads and by $T$ and outcome of tails, then the possible outcomes for the six coin flips can be represented by a sequence of six letters, with each letter being either a $T$ or an $H$. For example $HHHHHH$ would represent the case where all six coin tosses come up heads. There are two choices for each letter and six letters so this gives $2^6 = 64$ possible outcomes.

To see more clearly why the two possibilities for the first toss need to be multiplied by the two possibilities for the second toss observe that each outcome, $H$ or $T$ for the first toss, leads to two possible outcomes when paired with the second toss: $H$ leads to $HH$ and $HT$ while $T$ leads to $TH$ and $TT$. This reasoning for multiplying by two for each additional coin toss leads to $2^6$ possibilities if the coin is tossed six times.

2. For $f(6)$ to be zero, there need to be the same number of steps to the left as to the right. So there must be $3$ heads and $3$ tails. We can make a list of the possibilities. To simplify the list, we will list the possibilities for which tosses came up heads so that $123$ will mean that the first, second, and third tosses were heads while the fourth, fifth, and sixth were tails: $$\begin{array}{c} 123,124,125,126,134,135,136,145,146,156,234,235,236,\\ 245,246,256, 345,346,356,456. \end{array}$$ There are twenty possibilities so the probability that $f(6) = 0$ is $\frac{20}{64}$.

A word is worthwhile regarding the way in which the possible ways three heads could occur was listed above. The list is long and so to avoid duplication and to make sure the list is complete a method is useful. The list above has been formed by choosing the smallest first number (this is why the first ten numbers in the list begin with a $1$), then the smallest possible second number, and finally the smallest third number.

In order for $f(6)$ to be one there would need to be one more occurrence of heads than tails. But this means that the total number of coin tosses would have to be odd: if $n$ is any whole number then $n + (n+1) = 2n+1$ is an odd number. Therefore the probability that $f(6) = 1$ is $0$. The argument for why $f(6)$ can never equal $1$ is essentially the same as the argument in ''Random Walk II'' for why it is not possible for $f(7)$ to be equal to $2$.

Finally for the probability that $f(6) = 6$. This means that Scott must have moved in the positive direction after each of the six coin tosses so all six coin tosses must have been heads. So this can happen in only one way while there are $2^6 = 64$ different possible outcomes for the six coin tosses so the probability that $f(6) = 6$ is $\frac{1}{64}$.

3. The bar graph below shows the probabilities for the different possible outcomes. In part (b) we found that the probability of landing on $0$ is $\frac{20}{64}$. The other possible landing points, with $6$ coin tosses are $\pm 2, \pm 4, \pm 6$. The probabilities for these are, respectively $\frac{15}{64}, \frac{6}{64}$, and $\frac{1}{64}$. This can be found making lists as in part (b) or with combinatorial symbols as in solution 2 below.

4. In part (c) the probability of each possible outcome has been calculated and the most likely spot for Scott to land on after his walk is zero.

Solution: 2. Using Combinatorial symbols to calculate probabilities

Here we give an alternative approach to parts (b) and (c) of the problem. If $a$ and $b$ are positive whole numbers with $a \geq b$ the combinatorial symbol $$\left( \begin{array}{c} a \\b \end{array}\right)$$ denotes the number of collections of $a$ objects which can be chosen from a collection of $b$ objects. Many textbooks use the symbol $_aC_b$ (said ''$a$ choose $b$'') to denote this quantity: $$_aC_b = \left( \begin{array}{c} a \\b \end{array}\right).$$ For example, $$_6C_1 = \left( \begin{array}{c} 6\\1 \end{array}\right) = 6$$ since there are $6$ different objects which could be chosen from a collection of $6$. We can also see that $$_6C_2 = \left( \begin{array}{c} 6 \\2 \end{array}\right) =15$$ because there are $6$ choices of a first object $x_1$, $5$ choices left for the second object $x_2$, but each pair $\{x_1, x_2\}$ gets listed twice, once as $\{x_1,x_2\}$ and once as $\{x_2,x_1\}$. So the thirty choices of two objects gives $15$ different pairs. Finally, we study the case considered in part (b) of the problem $$_6C_3 = \left( \begin{array}{c} 6 \\3 \end{array}\right) = 20$$ as was seen in the first solution. Extending the explanation used for choosing one or two out of six, there are $6$ choices for a first object $x_1$, $5$ choices for a second object $x_2$, and $4$ choice for a third object $x_3$. Then there are $6$ ways to list this triplet: $$\{x_1,x_2,x_3\}, \{x_1,x_3,x_2\}, \{x_2,x_1,x_3\}, \{x_2,x_3,x_1\}, \{x_3,x_1,x_2\}, \{x_3,x_2,x_1\}.$$ It is important to note, for the generalization to follow, that $6 = 3 \cdot 2$: the $6$ different ways of listing $x_1,x_2,x_3$ come from the fact that there are $3$ choices for what goes first and then two choices for what goes second (and only one choice for what goes last).

In general to find $$\left( \begin{array}{c} a \\b \end{array}\right)$$ we can extend the method used above when $a = 6$ and $b = 3$. There are $a$ choices for a first object, $a-1$ for a second, and so on with $a - b+ 1$ for the $b^{\rm th}$ object. Each collection of $b$ objects gets counted $b(b-1)\cdot \ldots \cdot 1$ times, with $b$ choices for the first element of the set, $b-1$ for the second, and so on. Thus we have found $$\left( \begin{array}{c} a \\b \end{array}\right) = \frac{a(a-1) \cdot \ldots \cdot (a-b+1)}{b \cdot (b-1) \cdot \ldots \cdot 1}.$$

Now that we have a general formula, we can apply this to the situation considered here in Scott's random walk. For part (b) we know that $f(6) = 0$ if there are $3$ heads and $3$ tails. So the number of ways this can happen is $$\left( \begin{array}{c} 6 \\3 \end{array}\right) =\frac{6 \cdot 5 \cdot 4}{3 \cdot 2 \cdot 1} = 20$$ giving a probability of $\frac{20}{64}$ of having $3$ heads and $3$ tails. The probability of landing on $6$ is the same as the probility of having $6$ heads and this is $$\left( \begin{array}{c} 6 \\6 \end{array}\right) = \frac{6 \cdot 5 \cdot 4 \cdot 3 \cdot 3 \cdot 1}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 1$$ possibility out of $64$.

All of the probabilities in part (c) can be calculated in the same way using the general formula for calculating combinations.