 Solution

ID: past-exam-of-the-algorithmic-foundations-of-learning-course-of-the-university-of-oxford/2025/3/b/ii/solution

Use the first order statistic and correct its bias:

θ (X) = X_{(1)} - \frac{1}{n + 1}, X_{(1)} = min_{1 \leq i \leq n} X_{i} .

This is a measurable function of the sample. Under

U_{θ}^{n}

, write

Z = X_{(1)} - θ

. It lies in

[0, 1]

P_{θ} (Z > u) = \prod_{i = 1}^{n} P_{θ} (X_{i} > θ + u) = (1 - u)^{n}, 0 \leq u \leq 1.

For a bounded nonnegative random variable, integrating the identities

Z = \int_{0}^{1} 1_{{Z > u}} d u

and

Z^{2} = \int_{0}^{1} 2 u 1_{{Z > u}} d u

E_{θ} Z E_{θ} Z^{2} = \int_{0}^{1} (1 - u)^{n} d u = \frac{1}{n + 1}, = 2 \int_{0}^{1} u (1 - u)^{n} d u = 2 (\frac{1}{n + 1} - \frac{1}{n + 2}) = \frac{2}{( n + 1 ) ( n + 2 )} .

Thus

θ

Z

, independent of

θ

E_{θ} (θ - θ)^{2} = \frac{2}{( n + 1 ) ( n + 2 )} - \frac{1}{( n + 1 ) ^{2}} = \frac{n}{( n + 1 ) ^{2} ( n + 2 )} .

Taking the supremum over all real

θ

and then the infimum over estimators gives

m_{n} \leq \frac{n}{( n + 1 ) ^{2} ( n + 2 )} \leq \frac{1}{n ^{2}}, C^{'} = 1.

The final inequality follows from

n^{3} \leq (n + 1)^{2} (n + 2)

. Together with part (i), this proves that the minimax risk has order

n^{- 2}

for all

n \geq 1

. In the last line of the source, the request for the upper-bound constant calls it

C

; here it is denoted

C^{'}

consistently with the upper-bound inequality.

 New to topics? Read the docs here!