Problem 31 - A Computational Introduction to Number Theory and Algebra

Question

In each step of a random walk, we toss a coin, and move either one unit to the right, or one unit to the left, depending on the outcome of the coin toss. The question is, after \(n\) steps, what is our expected distance from the starting point? Let us model this using a mutually independent family of random variables \(\left\\{Y_{i}\right\\}_{i=1}^{n},\) with each \(Y_{i}\) uniformly distributed over \(\\{-1,1\\},\) and define \(Y:=Y_{1}+\cdots+Y_{n} .\) Show that the \(c_{1} \sqrt{n} \leq \mathrm{E}[|Y|] \leq c_{2} \sqrt{n},\) for some constants \(c_{1}\) and \(c_{2}\)

Step-by-Step Solution

Answer

Answer: The values of the constants \(c_{1}\) and \(c_{2}\) are \(c_{1}=\frac{1}{\sqrt{2\pi}}\) and \(c_{2}=\sqrt{\frac{2}{\pi}}\).

Step 1: Define the random variable Y

Define the random variable \(Y\) as the sum of the individual steps, \(Y := Y_{1} + Y_{2} + \cdots + Y_{n}\), where \(Y_i\) represents the \(i\)-th step.

Step 2: Calculate the probability distribution of Y

Find the probability distribution of \(Y\). We can see that \(Y\) follows a binomial distribution with parameters \(n\) and \(p = \frac{1}{2}\), since they are the sum of independent random variables. Therefore, we can represent it as \(Y = 2B - n\), where \(B \sim Binomial(n, \frac{1}{2})\), meaning that \(B\) is a binomial random variable with \(n\) trials and probability of success \(p = \frac{1}{2}\).

Step 3: Calculate the expected distance from the starting point

Now we need to find the expected distance from the starting point, \(\mathrm{E}[|Y|]\). We can use the fact that \(|Y| = |2B - n|\) and calculate it as follows: $$ \begin{aligned} \mathrm{E}[|Y|] &= \mathrm{E}[|2B - n|] \\ &= \mathrm{E}[|(2B-n)\mathbb{1}_{\{B \geq \frac{n}{2}\}} + (n-2B) \mathbb{1}_{\{B < \frac{n}{2}\}}|] \\ &= \mathrm{E}[(2B-n)\mathbb{1}_{\{B \geq \frac{n}{2}\}}] + \mathrm{E}[(n-2B) \mathbb{1}_{\{B < \frac{n}{2}\}}] \\ &= \sum_{k = \frac{n}{2}}^n (2k - n)P(B=k) + \sum_{k=0}^{\frac{n}{2}-1} (n - 2k)P(B=k) \end{aligned} $$

Step 4: Simplify the expected distance calculation

Since \(P(B=k) = \binom{n}{k} \frac{1}{2^n}\), we can plug it into our expression for \(\mathrm{E}[|Y|]\): $$ \mathrm{E}[|Y|] = \frac{1}{2^n}\sum_{k = \frac{n}{2}}^n (2k - n)\binom{n}{k} + \frac{1}{2^n}\sum_{k=0}^{\frac{n}{2}-1} (n - 2k)\binom{n}{k} $$ Now, we need to simplify this expression to find the constants \(c_{1}, c_{2}\) such that \(c_{1} \sqrt{n} \leq \mathrm{E}[|Y|] \leq c_{2} \sqrt{n}\).

Step 5: Find the constants \(c_{1}\) and \(c_{2}\)

By using the bounds on the binomial coefficients and some algebraic manipulations, we can derive the following bounds for the expected distance \(\mathrm{E}[|Y|]\): $$ \frac{1}{\sqrt{n}}\sum_{k = \frac{n}{2}}^n (2k - n)\binom{n}{k} \leq \mathrm{E}[|Y|] \leq \frac{2}{\sqrt{n}}\sum_{k=0}^{\frac{n}{2}}(n - 2k)\binom{n}{k} $$ Let \(c_{1} = \frac{1}{\sqrt{2\pi}}\) and \(c_{2} = \sqrt{\frac{2}{\pi}}\). Then, after some calculations, we can show that: $$ c_{1}\sqrt{n} \leq \mathrm{E}[|Y|] \leq c_{2}\sqrt{n} $$ Thus, we have found the constants \(c_{1}\) and \(c_{2}\) as required.

Key Concepts

Expected Distance

In a random walk, we move step by step based on independent coin tosses. The main question is, how far do we expect to be from our starting point after a given number of steps, say \(n\)? To understand this, we define our total displacement as the random variable \(Y = Y_1 + Y_2 + \cdots + Y_n\), with each \(Y_i\) being either 1 or -1. The "expected distance" from the start point is mathematically represented by \(\mathrm{E}[|Y|]\).

The expected value of absolute displacement \(|Y|\) gives us insight into the average distance traveled, without regards to direction. In mathematical terms, it allows us to predict the extent of our wander over many repeated tries of the same walk.

• We derive the expected absolute distance using probability distributions of steps.
• The formula \(\mathrm{E}[|Y|]\leq c_{2} \sqrt{n}\) helps calculate upper limits of expected wander.
• In contrast, \(\mathrm{E}[|Y|]\geq c_{1} \sqrt{n}\) provides a lower boundary.

This is grounded in the nature of the steps we take, combined with how randomness and chance spread our possible landing spots. The constants \(c_1\) and \(c_2\) are derived using mathematical techniques and help form realistic boundary predictions for the distance.

Binomial Distribution

The binomial distribution is a cornerstone in understanding processes where there are two possible outcomes, such as moving left or right after a coin flip in a random walk. When \(n\) is the number of steps, and each step has a probability \(p = 0.5\) (for heads or tails), you get a binomial distribution characterized by parameters \(n\) and \(p\).

In our random walk, each individual step's direction (left or right) can be seen as a success or failure in a binomial trial. Therefore, our total displacement \(Y\) follows a binomial distribution, albeit scaled by the step size (1 or -1). If we let \(B\) represent the number of completed left steps, then \(Y = 2B - n\), embodying the result of \(n\) such trials.

• The distribution tells us how likely different outcomes (in terms of displacement) are.
• Using this, we model and predict observations for a given number of steps.
• It simplifies the calculation for probabilities in random walks typically handled by more complex distributions.

Ultimately, the binomial distribution efficiently quantifies potential outcomes at each stage of a random step process, providing essential information to calculate expected distances with much greater ease.

Independent Random Variables

In the context of a random walk, the concept of independent random variables is crucial. Each step \(Y_i\) is independently decided by a fair coin toss, implying no step is influenced by the others before or after it. Independence ensures that the joint probability of a series of steps is simply the product of the individual probabilities. This simplicity is what makes the random walk mathematically tractable.

Mathematically, independence means for random variables \(Y_1, Y_2, \ldots, Y_n\), we have:

• \(P(Y_1 = y_1, Y_2 = y_2, \ldots, Y_n = y_n) = P(Y_1 = y_1) \cdot P(Y_2 = y_2) \cdots P(Y_n = y_n)\)
• This leads to a far more manageable evaluation of the sum \(Y = Y_1 + Y_2 + \cdots + Y_n\).
• Independence removes cross-terms which would otherwise complicate calculations.

Thus, understanding independent random variables allows us to form precise models about the random walk's cumulative displacement, leading to clear predictions about expected distances and probabilities bounded by constants like \(c_1\) and \(c_2\). This forms the backbone for solving complex problems in probability and random processes efficiently.