HL AA Paper 3 Practice

Step 1. Apply $T$ repeatedly.

Observation: the orbit is a period-2 cycle $\tfrac{1}{3} \to \tfrac{2}{3} \to \tfrac{1}{3} \to \ldots$ (A1 · A1 · A1)

Setup. By definition, $x_0 = \sum_{i=1}^{\infty} b_i \, 2^{-i}$.

Case split.

• If $b_1 = 0$: $x_0 < \tfrac12$, so $x_1 = 2x_0 = 0.b_2 b_3 \ldots_2$. (M1)
• If $b_1 = 1$: $x_0 \ge \tfrac12$, so $x_1 = 2x_0 - 1 = b_1 + 0.b_2 b_3 \ldots_2 - 1 = 0.b_2 b_3 \ldots_2$. (M1)

In both cases $x_1 = 0.b_2 b_3 b_4 \ldots_2$ — the doubling map is a binary shift. (R1 · AG1)

Argument. A rational has a binary expansion that is either terminating or eventually periodic. (R1)

By part (b), $T$ shifts this expansion left by one bit each step, so after finitely many applications the tail is purely periodic; the orbit then repeats every $p$ steps where $p$ is the binary period. (R1 · A1)

Setup. Because the doubling map is a binary shift (part b), the difference in the first surviving bit is what matters after $n$ shifts.

Initial difference: agreeing on bits 1–4, differing at bit 5. So $|x_0 - y_0| \le 2^{-4}$. (M1)

After $n$ applications of $T$, the leading disagreeing bit is at position $5 - n$. In general, $|x_n - y_n|$ can double each step (approximately). (M1)

• $n=1$: bits 4 disagree ⇒ $|x_1 - y_1| \le 2^{-3} = \tfrac{1}{8}$
• $n=2$: bits 3 disagree ⇒ $|x_2 - y_2| \le 2^{-2} = \tfrac{1}{4}$
• $n=3$: bits 2 disagree ⇒ $|x_3 - y_3| \le \tfrac{1}{2}$
• $n=4$: bits 1 disagree; the numbers are macroscopically apart. (A1 · A1)

Sensitivity to initial conditions: tiny changes in the starting point ($\le 2^{-4}$) grow to differences of $\ge \tfrac{1}{4}$ within 4 steps — a signature of chaos. (R1)

Base case ($k = 0$): $x_0 = 2^0 x_0 = x_0$. Trivially true. (M1)

Inductive step. Assume $x_j = 2^j x_0$ for some $0 \le j < k$. Because bits $b_1, \ldots, b_k$ are all $0$, $x_j$ has its bit-$1$ position equal to $b_{j+1} = 0$, so $x_j < \tfrac12$. (M1)

Conclusion. By induction, $x_k = 2^k x_0$ for all $0 \le k \le$ (first non-zero bit position). (R1 · AG1 · A1)

Compute $T'$. On each of $[0, \tfrac12)$ and $[\tfrac12, 1)$, $T(x)$ is linear with slope $2$. So $T'(x) = 2$ wherever it exists. (M1 · A1)

Apply the definition.

Interpretation. A positive Lyapunov exponent ($\ln 2 \approx 0.693$) confirms the chaos observed in (d): nearby orbits diverge exponentially fast, doubling their separation each step. (R1 · AG1)

Argument. By part (b), each application of $T$ discards one bit of the initial condition. After $n$ steps, the current state depends only on bits $b_{n+1}, b_{n+2}, \ldots$ of $x_0$. (R1)

In practice we know $x_0$ only to finite precision — say $B$ bits. After $B$ iterations, all known information about $x_0$ has been "shifted out"; the future orbit is determined by bits we never measured. (R1)

Equivalently, from part (f), errors grow by a factor of $2$ per step ($e^{\lambda} = 2$). Any starting-value uncertainty of $2^{-B}$ becomes $O(1)$ after $B$ steps. (R1 · A1)

From each vertex the robot goes to the other two with probability $\tfrac12$, and to itself with probability $0$.

Use symmetry. Since $q_n = r_n$ and $p_n + q_n + r_n = 1$, we have $q_n = r_n = \tfrac{1-p_n}{2}$. (M1)

Compute $p_{n+1}$. The robot arrives at $A$ from $B$ or $C$ with probability $\tfrac12$ each:

Hence $p_{n+1} = \tfrac12(1 - p_n)$. (M1 · A1 · AG1)

Find the fixed point. Setting $p^* = \tfrac12(1 - p^*)$ gives $p^* = \tfrac13$. (M1)

Substitute $u_n = p_n - \tfrac13$.

So $u_n$ is geometric with ratio $-\tfrac12$ and $u_0 = 1 - \tfrac13 = \tfrac23$. (M1 · A1)

Closed form.

$\left(-\tfrac12\right)^n \to 0$ as $n \to \infty$, so $p_n \to \tfrac13$ and by symmetry $q_n, r_n \to \tfrac13$. (M1)

Interpretation: in the long run the robot is equally likely to be at any vertex, regardless of where it started. (R1)

Eigenvalue interpretation. Any state vector can be decomposed as a linear combination of eigenvectors: one along the $\lambda = 1$ eigenspace (the stationary distribution $(\tfrac13, \tfrac13, \tfrac13)^{\mathrm T}$), the rest along the $\lambda = -\tfrac12$ eigenspace. (R1)

After $n$ applications of $M$, the $\lambda = 1$ component is unchanged, and the transient components are multiplied by $(-\tfrac12)^n$. (R1)

• Long-run limit: as $n \to \infty$, $(-\tfrac12)^n \to 0$, leaving only the stationary distribution — matches (e). (A1)
• Decay rate: convergence is geometric with ratio $|\lambda_2| = \tfrac12$ — matches the closed form in (d), where the transient term $\tfrac23(-\tfrac12)^n$ decays by exactly a factor of $\tfrac12$ each step. (A1)

New transition matrix.

Since $M$ has eigenvalues $1, -\tfrac12, -\tfrac12$, $M_b$ has eigenvalues $b + (1-b)\lambda$ — so $1$ (unchanged, since $b + (1-b)\cdot 1 = 1$) and $b - \tfrac{1-b}{2} = \tfrac{3b - 1}{2}$ (transient). (M1 · A1)

Decay to $10^{-3}$. Require $|\tfrac{3b-1}{2}|^n < 10^{-3}$. With $b = 0.9$, transient eigenvalue is $\tfrac{1.7}{2} = 0.85$:

So about $43$ steps. Compare with the unbiased robot ($b = 0$, transient eigenvalue $\tfrac12$): $0.5^n < 10^{-3} \Rightarrow n \ge 10$. The bias dramatically slows convergence. (M1 · A1)