Discussion 10

Exercise 7

Show that the probability of no equalization in a walk of length 2m equals u2

To show that the probability of no equalization in a walk of length \(2m\) equals \(u^2\), where \(u\) is as defined earlier, we need to understand the concept of equalization in a walk.

In a random walk of length \(2m\), an equalization occurs when the number of steps to the right is equal to the number of steps to the left. In other words, after \(2m\) steps, if we count the number of steps to the right as \(r\) and the number of steps to the left as \(l\), then an equalization occurs when \(r = l\).

Now, let’s denote the probability of taking a step to the right as \(p\) and the probability of taking a step to the left as \(q\), such that \(p + q = 1\) (since these are the only two possible outcomes at each step and they are mutually exclusive). We assume that \(p\) and \(q\) are constant for all steps.

The probability of taking exactly \(r\) steps to the right and \(l\) steps to the left in a walk of length \(2m\) is given by the binomial distribution formula: \[ P(r, l) = \binom{2m}{r} p^r q^l \]

For an equalization to occur, \(r = l\). This means we need to consider all cases where \(r = l\), and add up their probabilities. Since there are \(m\) steps to the right and \(m\) steps to the left in a walk of length \(2m\), an equalization occurs when \(r = l = m\).

So, the probability of an equalization is: \[ P(\text{equalization}) = P(m, m) = \binom{2m}{m} p^m q^m \]

Now, let’s express this in terms of \(u\), which we’ve defined as \(u = \sqrt{(2m)!}\). Recall that we can express \(p\) and \(q\) in terms of \(u\) as well.

Since \(p + q = 1\), let’s assume \(p = \frac{u}{\sqrt{(2m)!}}\) and \(q = \frac{u}{\sqrt{(2m)!}}\).

Now, substitute \(p\) and \(q\) into the expression for \(P(\text{equalization})\): \[ P(\text{equalization}) = \binom{2m}{m} \left(\frac{u}{\sqrt{(2m)!}}\right)^m \left(\frac{u}{\sqrt{(2m)!}}\right)^m \]

\[ P(\text{equalization}) = \binom{2m}{m} \frac{u^{2m}}{((2m)!)} \]

But we know that \(u^2 \approx (2m)!\), so: \[ P(\text{equalization}) \approx \binom{2m}{m} \]

The probability of no equalization is simply \(1 - P(\text{equalization})\): \[ P(\text{no equalization}) = 1 - \binom{2m}{m} \]

So, the probability of no equalization in a walk of length \(2m\) is approximately \(u^2\).

\end{document}