HL AA Paper 3 Practice

Question 1 · The doubling map and chaotic dynamics

Topics: functions, iteration, sequences, logarithms · 28 marks

Define the doubling map $T : [0, 1) \to [0, 1)$ by

$T (x) = 2 x mod 1 = {\begin{cases} 2 x & if 0 \leq x < \frac{1}{2} \\ 2 x - 1 & if \frac{1}{2} \leq x < 1 \end{cases}$

The orbit of a starting point $x_{0}$ is the sequence $x_{0}, x_{1}, x_{2}, \dots$ where $x_{n + 1} = T (x_{n})$ . Throughout this question you may express numbers in binary using the notation $0. b_{1} b_{2} b_{3} \dots_{2}$ where each $b_{i} \in {0, 1}$ .

(a) [3 marks]

Compute the first five terms of the orbit starting at $x_{0} = \frac{1}{3}$ .

Reveal worked solution

Step 1. Apply $T$ repeatedly.

x_{1} = T (\frac{1}{3}) = \frac{2}{3}

(since

\frac{1}{3} < \frac{1}{2}

)

x_{2} = T (\frac{2}{3}) = 2 \cdot \frac{2}{3} - 1 = \frac{1}{3}

x_{3} = T (\frac{1}{3}) = \frac{2}{3}, x_{4} = \frac{1}{3}

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

(b) [4 marks]

Let $x_{0} = 0. b_{1} b_{2} b_{3} \dots_{2}$ be a binary expansion. Prove that $x_{1} = T (x_{0}) = 0. b_{2} b_{3} b_{4} \dots_{2}$ .

Reveal worked solution

This worked solution is for subscribers.

The first worked solution is free — enough to see our teaching style. Subscribe once for €49 to unlock every reasoned solution across your course, plus AI grading, mark schemes and 200+ PDF workbooks. Real understanding, not just answers.

Unlock full solutions →

Deduce that every rational $x_{0} \in (0, 1)$ has an eventually periodic orbit.

Reveal worked solution

This worked solution is for subscribers.

Unlock full solutions →

(d) [5 marks]

Two starting points $x_{0} = 0.0101 {\overset{―}{01}}_{2}$ and $y_{0} = 0.0101 {\overset{―}{10}}_{2}$ differ from the 5th binary digit onwards. Prove that after $n$ applications of $T$ , $| x_{n} - y_{n} | \leq 2^{- (4 - n)}$ for $n \leq 4$ , and that the orbits diverge to be at least $\frac{1}{4}$ apart by step 4.

Reveal worked solution

This worked solution is for subscribers.

Unlock full solutions →

(e) [5 marks]

Prove by mathematical induction that for any $x_{0} \in [0, 1)$ whose binary expansion starts with $k$ zeros ( $b_{1} = b_{2} = \dots = b_{k} = 0$ ), $x_{k} = 2^{k} x_{0}$ .

Reveal worked solution

This worked solution is for subscribers.

Unlock full solutions →

(f) [4 marks]

The Lyapunov exponent of the doubling map at $x_{0}$ is defined as $λ (x_{0}) = lim_{n \to \infty} \frac{1}{n} \sum_{i = 0}^{n - 1} \ln | T^{'} (x_{i}) |$ wherever $T^{'}$ exists. Show that $λ (x_{0}) = \ln 2$ for every $x_{0}$ where the derivative is defined.

Reveal worked solution

This worked solution is for subscribers.

Unlock full solutions →

(g) [4 marks]

Explain, using parts (b) and (f), why despite being deterministic the doubling map is unpredictable in practice.

Reveal worked solution

This worked solution is for subscribers.

Unlock full solutions →

Question 2 · Random walk on a triangle

Topics: probability, matrices, sequences, limits · 27 marks

A robot sits at one of three vertices of an equilateral triangle labelled $A$ , $B$ , $C$ . At each step the robot moves to one of the other two vertices with probability $\frac{1}{2}$ each, independently of past moves. Let $p_{n}$ , $q_{n}$ , $r_{n}$ denote the probability that the robot is at $A$ , $B$ , $C$ respectively after $n$ steps.

Let $v_{n} = (\begin{matrix} p_{n} \\ q_{n} \\ r_{n} \end{matrix})$ be the state vector at step $n$ .

(a) [3 marks]

Write down the transition matrix $M$ such that $v_{n + 1} = M v_{n}$ .

Reveal worked solution

This worked solution is for subscribers.

Unlock full solutions →

(b) [3 marks]

The robot starts at $A$ : $v_{0} = (1, 0, 0)^{T}$ . Compute $v_{1}$ , $v_{2}$ and $v_{3}$ .

Reveal worked solution

This worked solution is for subscribers.

Unlock full solutions →

By symmetry, $q_{n} = r_{n}$ for all $n \geq 1$ . Show that $p_{n + 1} = 1 - p_{n} - \frac{1}{2} (1 - p_{n})$ and deduce the recurrence $p_{n + 1} = \frac{1}{2} (1 - p_{n})$ .

Reveal worked solution

This worked solution is for subscribers.

Unlock full solutions →

(d) [6 marks]

Solve the recurrence $p_{n + 1} = \frac{1}{2} (1 - p_{n})$ with $p_{0} = 1$ to obtain a closed form for $p_{n}$ .

Reveal worked solution

This worked solution is for subscribers.

Unlock full solutions →

(e) [3 marks]

Deduce $lim_{n \to \infty} v_{n}$ and interpret it.

Reveal worked solution

This worked solution is for subscribers.

Unlock full solutions →

(f) [4 marks]

The matrix $M$ has eigenvalues $λ_{1} = 1$ and $λ_{2} = λ_{3} = - \frac{1}{2}$ . Explain — without diagonalising $M$ — how the eigenvalues predict both the long-run limit in (e) and the geometric decay rate in (d).

Reveal worked solution

This worked solution is for subscribers.

Unlock full solutions →

(g) [4 marks]

A biased robot now stays put with probability $b \in [0, 1)$ and moves to each other vertex with probability $\frac{1 - b}{2}$ . Predict the new dominant transient eigenvalue as a function of $b$ , and hence how many steps roughly are needed for the state to be within $10^{- 3}$ of the stationary distribution when $b = 0.9$ .

Reveal worked solution

This worked solution is for subscribers.

Unlock full solutions →

Want unlimited Paper 3 practice targeted at your weakest sub-topics?

Order a Personalised Paper 3 set — €5 for one, delivered as a PDF within 48 hours.

Summer Revision — €20, everything included

Question 1 · The doubling map and chaotic dynamics

Question 2 · Random walk on a triangle