Chapter 0: EG.4 Solution

Working problems is a crucial part of learning mathematics. No one can learn topology merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

$^{*}$ (Continuation) Suppose now that the elements $a$ , $a^{-1}$ , $b$ , $b^{-1}$ are chosen instead with respective probabilities $\alpha$ , $\alpha$ , $\beta$ , $\beta$ , where $\alpha>0$ , $\beta>0$ , $\alpha+\beta=\tfrac{1}{2}$ . Prove that the conditional probability that the reduced word 1 ever occurs at a positive time, given that the element $a$ is chosen at time 1, is the unique root $x=r(\alpha)$ (say) in $(0,1)$ of the equation $3x^{3}+(3-4\alpha^{-1})x^{2}+x+1=0.$ As time goes on, (it is almost surely true that) more and more of the reduced word becomes fixed, so that a final word is built up. If in the final word, the symbols $a$ and $a^{-1}$ are both replaced by $A$ and the symbols $b$ and $b^{-1}$ are both replaced by $B$ , show that the sequence of A’s and B’s obtained is a Markov chain on $\{A,B\}$ with (for example) $p_{AA}=\frac{\alpha(1-x)}{\alpha(1-x)+2\beta(1-y)},$ where $y=r(\beta)$ . What is the (almost sure) limiting proportion of occurrence of the symbol $a$ in the final word? (Note. This result was used by Professor Lyons of Edinburgh to solve a long-standing problem in potential theory on Riemannian manifolds.)

Let $p_{*}$ be the probability of returning to $1$ from word $*$ , and let $p_{*}^{(k)}$ be the probability that it first happens in $k$ steps. Then, $\begin{eqnarray*} p_{\alpha\alpha} & = & \sum_{k=1}^{\infty}p_{\alpha}^{(k)}\cdot p_{\alpha}\\ & = & p_{\alpha}^{2},\\ p_{\alpha\beta} & = & \sum_{k=1}^{\infty}p_{\beta}^{(k)}\cdot p_{\alpha}\\ & = & p_{\alpha}\cdot p_{\beta},\\ p_{\alpha\beta^{-1}} & = & \sum_{k=1}^{\infty}p_{\beta^{-1}}^{(k)}\cdot p_{\alpha}\\ & = & p_{\alpha}\cdot p_{\beta^{-1}}. \end{eqnarray*}$ And similarly for $p_{\beta\alpha}$ , $p_{\beta\alpha^{-1}}$ , and $p_{\beta\beta}$ . Note that $p_{\beta^{-1}}=p_{\beta}$ . Therefore, $\begin{eqnarray*} p_{\alpha} & = & \alpha+\alpha p_{\alpha}^{2}+2\beta p_{\alpha}p_{\beta},\\ p_{\beta} & = & \beta+\beta p_{\beta}^{2}+2\alpha p_{\alpha}p_{\beta}. \end{eqnarray*}$ Further, $\begin{eqnarray*} \alpha(1-p_{\alpha})^{2} & = & 2\beta p_{\alpha}(1-p_{\beta}),\\ \beta(1-p_{\beta})^{2} & = & 2\alpha p_{\beta}(1-p_{\alpha}). \end{eqnarray*}$ And, we have $\begin{eqnarray*} \alpha^{2}(1-p_{\alpha}^{2})^{2} & = & 4p_{\alpha}^{2}[\beta(1-p_{\beta})+\alpha(1-p_{\alpha})]^{2}\\ & = & 4p_{\alpha}^{2}[\beta+\alpha(1-p_{\alpha})]^{2}-4\beta^{2}p_{\alpha}^{2}\\ & = & 4\alpha p_{\alpha}^{2}(1-\alpha-\alpha p_{\alpha})(1-p_{\alpha}),\\ 0 & = & \alpha^{2}(1-p_{\alpha})[1+p_{\alpha}+(3-4\alpha^{-1})p_{\alpha}^{2}+3p_{\alpha}^{3}]. \end{eqnarray*}$ Note that if we exchange $\alpha$ and $\beta$ in the initial equations, we get exactly the same system of equations, meaning that $p_{\beta}$ satisfies a similar equation with $\beta$ instead of $\alpha$ . Again, we need to argue that $p_{\alpha}<1$ , so that $p_{\alpha}$ is the root of the cubic equation in $(0,1)$ . The fact that this root exists and is unique follows from the fact that the polynomial is $1$ at $0$ , and $8-\tfrac{4}{\alpha}<0$ at $1$ .

Consider a sequence of symbols such that $a$ is finally placed at some position. Then, the following sequence is such that whenever it reduces to the empty word, $a^{-1}$ is not placed as the next symbol. If $a$ is placed (with the probability $\tfrac{\alpha}{1-\alpha}$ ), then it has the probability $1-r(\alpha)$ of staying at that position forever. Similarly, if $b$ or $b^{-1}$ is added (each with probability $\tfrac{\beta}{1-\alpha}$ ), then it has the probability of staying $1-r(\beta)$ . Hence, conditional on that the next symbol is final, $\left\{ \begin{array}{ccc} P_{AA} & \sim & \alpha(1-r(\alpha)),\\ P_{AB} & \sim & 2\beta(1-r(\beta)). \end{array}\right.$ Similarly, $\left\{ \begin{array}{ccc} P_{BA} & \sim & 2\alpha(1-r(\alpha)),\\ P_{BB} & \sim & \beta(1-r(\beta)), \end{array}\right.$ so that we get the desired result.

Finally, the proportion of $a$ is $\tfrac{1}{2}$ of the limit probability of $A$ , i.e. $\begin{eqnarray*} \tfrac{1}{2}\pi_{A} & = & \tfrac{1}{2}\tfrac{\tfrac{2\alpha(1-r(\alpha))}{2\alpha(1-r(\alpha))+\beta(1-r(\beta))}}{\tfrac{2\alpha(1-r(\alpha))}{2\alpha(1-r(\alpha))+\beta(1-r(\beta))}+\tfrac{2\beta(1-r(\beta))}{\alpha(1-r(\alpha))+2\beta(1-r(\beta))}}\\ & = & \tfrac{2r(\alpha)}{1+6r(\alpha)-3r(\alpha)^{2}},\\ \tfrac{1}{2}\pi_{B} & = & \tfrac{2r(\beta)}{1+6r(\beta)-3r(\beta)^{2}}. \end{eqnarray*}$

Subpages

Chapter 0: EG.4 Solution

Chapter 0: EG.4 Solution