Random Walk IV

Task

Imagine Scott stood at zero on a life-sized number line. His friend flipped a coin $100$ 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 100$, Scott's position on the number line after the $n^{\rm th}$ coin flip.

1. Before the tosses begin, where is Scott most likely to be after ten coin tosses?
2. Before the coin tosses begin, what is the most likely value for $f(15)$? Explain.
3. Before the coin tosses begin, what is the most likely value for $f(100)$? Explain.

IM Commentary

This task completes the line of reasoning of Random Walk III in a situation where the numbers become too large to calculate and so abstract reasoning is required in order to compare the different probabilities. It is intended for instructional purposes only with a goal of understanding how to calculate and compare the combinatorial symbols. Students who have not done ''The Random Walk'' should be encouraged to study what happens for some simple odd numbers of flips such as $1$, $3$, and $5$ before delving into part (b) of this question.

Whether or not combinatorial symbols are employed, work is needed in order to determine which of two numbers, say $$ \left( \begin{array}{c} 100 \\ 46 \end{array}\right), \,\,\, \left( \begin{array}{c} 100 \\42 \end{array}\right) $$ is larger. This can be done by thinking about the concrete meaning of these symbols in the context, namely collections of $46$ of the $100$ coins versus collections of $42$ of the $100$ coins. The first solution follows this path. The second solution is more algebraic and proceeds by analyzing the structure of the arithmetic expressions for the combinatorial symbols which were explained in the second solution to ''Random Walk III''.

Solutions

Solution: 1

1. In ''Random Walk III'' the most likely spot for Scott to be after six tosses was $0$ and, in fact, as the graph in the solution of that problem shows, the probabilities decrease for the possible outcomes as they move further away from $0$. A good starting guess, then, would be that the most likely landing place for Scott, in the ten toss case, is $0$. Following the analogy with ''Random Walk III,'' the next most likely outcomes would be $2$ and $-2$. So we will start by trying to show that he is more likely to land on $0$ than to land on $2$.

   Landing on $0$ means that exactly $5$ of the ten coins are tails while landing on $2$ means that $4$ of the ten coins are tails. Suppose we consider a concrete case where $4$ of the ten coins are tails, say the first, second, third, and fourth. We will denote this scenario by listing the coins which are tails: $$ \{1, 2, 3, 4\}. $$ We can find $6$ different combinations of $5$ tails that contain $\{1,2,3,4\}$, namely: $$ \{1,2,3,4,5\}, \{1,2,3,4,6\}, \{1,2,3,4,7\}, \{1,2,3,4,8\}, \{1,2,3,4,9\}, \{1,2,3,4,10\}. $$ There was nothing special about $\{1,2,3,4\}$ in this regard: any specific collection of four tails is contained in $6$ different collections of $5$ tails.

   It might be tempting to conclude that there are $6$ times the number collections of $5$ tails as there are collections of $4$ tails. This is not the case, however, because each collection of $5$ tails contains $5$ different collections of $4$ tails: for example, the set $\{1, 2, 3, 4, 5\}$ contains the five sets $$ \{1,2,3,4\}, \{1,2,3,5\}, \{1,2,4,5\}, \{1,3,4,5\}, \{2,3,4,5\}. $$ So there are not $6$ times as many five coin collections as there are four coin collections: when we multiplied the number of sets of $4$ tails by $6$, we over counted by a factor of $5$ (since each $5$ coin set of tails gets counted five different times, once for each $4$ coin set which it contains). So there are $\frac{6}{5}$ times as many combinations of the ten coin tosses giving $5$ heads as there are combinations giving $4$ heads.

   To check that this reasoning extends to other cases, we will compare the probability of getting $4$ tails with that of getting $3$ tails. For each collection of $3$ coins which are tails, there are $7$ collections of four coins containing this triplet. But each collection of $4$ tails contains $4$ different triplets of tails. Reasoning as above in comparing $5$ tail collections to $4$ tail collecitons, we conclude that there are $\frac{7}{4}$ times as many ways to get $4$ tails as there are to get $3$ tails. This structure persists all the way to the last step: there are $10$ choices for a single coin to be tails, only one choice to have no tails at all, and so it is $\frac{10}{1}$ times as likely to have one tails than it is to have none.

   We considered above the cases of $5$ tails, $4$ tails, and $3$ tails identifying a pattern which persists to the last step of $0$ tails. The same reasoning applies to $6$ tails, $7$ tails, and so on through $10$ tails. To see this, note that if a set of ten coin tosses moves Scott to $k$, then flipping all of the coins over would move Scott to $-k$ instead. So for each set of coin tosses which moves Scott to $k$ there is a corresponding set of tosses moving him to $-k$ making these two spots, $k$ and $-k$, equally likely finishing places for Scott's walk.

   Though not requested in the problem, a little bit of work with the above reasoning calculates the probabilities for different numbers of heads (or tails). No heads can only happen in one way so the probability of having no heads is $\frac{1}{2^{10}}$: the $2^{10}$ in the denominator comes from multiplying the two different outcomes for each of the ten coin flips. For one head, we multiply this by $\frac{10}{1}$ to get $\frac{10}{2^{10}}$. For two heads we multiply the outcomes for $1$ heads by $\frac{9}{2}$ to find $\frac{90}{2 \cdot 2^{10}} = \frac{45}{2^{10}}$. For three heads we multiply the number of possibilities for two heads by $\frac{8}{3}$ to get $\frac{120}{2^{10}}$. For four heads we multiply the three heads cases by $\frac{7}{4}$ to get $\frac{210}{2^{10}}$ and finally we need to multiply this last result by $\frac{6}{5}$ to get the most likely outcome of 5 heads which has a probability of $\frac{252}{2^{10}}$. We put all of this information in the table below:

   Point on Number Line	Probability of Landing Here
   $0$	$\frac{252}{1024}$
   $\pm 2$	$\frac{210}{1024}$
   $\pm 4$	$\frac{120}{1024}$
   $\pm 6$	$\frac{45}{1024}$
   $\pm 8$	$\frac{10}{1024}$
   $\pm 10$	$\frac{1}{1024}$

   The numbers in the table can also be found more readily as in the second solution below, using combinatorial symbols.

2. The case of fifteen coin flips is a little different from ten because fifteen is an odd number. It remains true, for the same reason, that landing on the spot $+k$ has the same likelihood of landing on the spot $-k$. Since $15$ is an odd number, Scott can only land on an odd number. As in part (a) with ten coin flips, to compare the likelihood of landing on $+1$ to $+3$ note that landing on $+1$ means $8$ heads and $7$ tails while landing on $+3$ means $9$ heads and $6$ tails. For each set of $6$ tails, there are $9$ collections of $7$ tails which contain the $6$ given ones. Each collection of $7$ tails contains $7$ different collections of $6$ tails so the number of choices of $7$ tails out of the fifteen coins is $\frac{9}{7}$ times the number of $6$ tails possibilities.

   We will do one more comparison for this example, looking at the possibilities with $6$ tails compared to those with $5$ tails. For each set of $5$ coins, there are $10$ collections of $6$ coins containing it. Each set of $6$ coins contains $6$ different sets of five coins so this means that the total number of sets of $6$ coins is $\frac{10}{6}$ times the number of sets of $5$ coins. As we continue lowering the number of tails by one, the numerator of the fraction goes up by one and the denominator down by one so the most likely outcome is to land on $+1$ or $-1$.

3. Since $100$ is an even number, the reasoning of (a) applies here. The most likely spot for Scott to be on afar the random walk is $0$. If we were to compare the likelihood of landing on $0$ versus landing on $+1$ or $-1$ he is $\frac{51}{50}$ times more likely to be on $0$. This means that the likelihood of landing on $0$ is only slightly larger than that of landing on $+1$ or $-1$. The likelihoods decrease more and more rapidly as one moves away from $0$.

Solution: 2. Combinatorial symbols

The reasoning in the first part of the solution can be applied in general to calculate the number of subsets of $b$ objects contained within a set of $a$ objects. It is nice, however, to have a shorthand for these important combinatorial numbers. We denote this quantity by

In the second solution to ''Random Walk II'' this quantity was computed and we found, for $0 \lt b \leq 10$, $$ \left( \begin{array}{c} 10 \\b \end{array}\right) = \frac{10\cdot 9 \cdot \ldots \cdot (10-b+1)}{b \cdot (b-1) \cdot \ldots \cdot 1} $$ The argument presented here uses the structure of this algebraic expression in order to compare the different probabilities for where Scott lands.

1. We need to evaluate the size of the combinatorial symbols with $a = 10$ and $b$ ranging from $0$ to $10$. The probability of $6$ heads is the same as the probability of $6$ tails which is the same as the probability of $4$ heads. This reasoning shows that $7$ heads and $3$ heads are equally likely as are $8$ heads and $2$ heads, $9$ heads and $1$ head, $10$ heads and $0$ heads. So we will only look at the combinatorial symbols when $0 \leq b \leq 5$. We first look at $b=5$ $$ \frac{10\cdot 9 \cdot 8 \cdot 7 \cdot 6}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} $$ compared to $b = 4$: $$ \frac{10\cdot 9 \cdot 8 \cdot 7 }{ 4 \cdot 3 \cdot 2 \cdot 1}. $$ These expressions are the same except for the extra $6$ in the numerator and $5$ in the denominator of $$\left( \begin{array}{c} 10 \\5 \end{array}\right). $$ So we can conclude, as in the first solution, that $$ \left( \begin{array}{c} 10 \\5 \end{array}\right) = \frac{6}{5}\left( \begin{array}{c} 10 \\4 \end{array}\right). $$

   Similarly to compare $$ \left( \begin{array}{c} 10 \\4 \end{array}\right) \,\,\,\, \text{and} \,\,\,\, \left( \begin{array}{c} 10 \\3 \end{array}\right) $$ there is an extra $7$ in the numerator and $4$ in the denominator of $$ \left( \begin{array}{c} 10 \\4 \end{array}\right) $$ making it $\frac{7}{4}$ times as big as $$ \left( \begin{array}{c} 10 \\3 \end{array}\right) . $$ The cases where $b = 2,1,0$ can be treated similarly. The advantage to this approach is that it is possible to see from the structure of the expressions where the fractions $\frac{6}{5}$, $\frac{7}{4}$ come from.

2. Combinatorial symbols are particularly efficient for dealing with larger numbers. To see, for example, that $$ \left( \begin{array}{c} 15 \\ 7 \end{array}\right) = \left( \begin{array}{c} 15 \\ 8 \end{array}\right) $$ we see that $$ \frac{15\cdot 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9}{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = \frac{15\cdot 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8}{8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} $$ because the $8$'s of the second fraction cancel to yield the first fraction.

   To compare the probability of getting $7$ heads versus the probability of getting $6$ heads, note that the expanded expression for $$ \left( \begin{array}{c} 15 \\ 7 \end{array}\right) $$ has an extra $8$ in the numerator and an extra $7$ in the denominator compared to $$ \left( \begin{array}{c} 15 \\ 6 \end{array}\right). $$ Thus we conclude that $$ \left( \begin{array}{c} 15 \\ 7 \end{array}\right) = \frac{8}{7} \left( \begin{array}{c} 15 \\ 6 \end{array}\right) $$ Similar analysis shows the string of inequalities $$ \left( \begin{array}{c} 15 \\ 6 \end{array}\right) > \left( \begin{array}{c} 15 \\ 5 \end{array}\right) > \left( \begin{array}{c} 15 \\ 4 \end{array}\right) > \left( \begin{array}{c} 15 \\ 3 \end{array}\right) > \left( \begin{array}{c} 15 \\ 2 \end{array}\right) > \left( \begin{array}{c} 15 \\ 1 \end{array}\right) > \left( \begin{array}{c} 15 \\ 0 \end{array}\right). $$

3. The case of one hundred coin flips resembles part (a) in that $0$ is the most likely spot for Scott to finish on since $100$ is an even number. The analysis of parts (a) and (b) allows us to see not only that $$ \left( \begin{array}{c} 100 \\ 50 \end{array}\right) > \left( \begin{array}{c} 100 \\ 49 \end{array}\right) $$ but allows to calculate the quotient of these two probabilities which is $\frac{51}{50}$. The same holds as the number of heads is successively decreased from $49$ down to $0$.