Past Exam 1

STAT 8670: Computational Methods in Statistics
Term: Fall 2025
Instructor: Chi-Kuang Yeh
Date: October 8, 2025
Total: 100 points

Exam Instructions

Note 1: Only a non-programmable calculator is allowed. Any other electronic devices are not allowed, and you would receive 0 for any usage of such a device during the exam.

Note 2: The maximum score is 100 points. If \(x\) is the total number of points earned, the recorded score is \(\min(100,x)\).

Note 3: Please write your answers on separate papers. Do NOT write on this paper, even for multiple choice. Any answers you write on this sheet will NOT count towards your grade!

Grade distribution

Question Content Points Score
1 Multiple Choice 18
2 Conceptual 20
3 Calculation 30
4 Algorithms 16
5 Convergence 16
Total 100

Question 1: Multiple Choice [18]

Each of the questions is worth [2] marks.

1a) [2]

In R, suppose

a = c(3, 2, 0)
b = c(1, 2, 3)

What is the output of cbind(a, b)?

  1. \[\begin{pmatrix} 3 & 1 \\ 2 & 2 \\ 0 & 3 \end{pmatrix}\]

  2. \[\begin{pmatrix} 3 & 2 & 0 \\ 1 & 2 & 3 \end{pmatrix}\]

  3. \[\begin{pmatrix} 3 & 2 \\ 0 & 1 \\ 2 & 3 \end{pmatrix}\]

  4. \[\begin{pmatrix} 1 & 3 \\ 2 & 2 \\ 3 & 0 \end{pmatrix}\]

A

1b) [2]

List is one of the most important object type in R. In R, suppose

x = list(a = 1:3, b = "hello")

What is the output of print(x)?

  1.  $a
 [1] 1 2 3
 $b
 [1] "hello"
  2.  [1] 1 2 3 "hello"
  3.  a b 
 1 2 3 
 "hello"
  4.  $1
 [1] "a" "b"

A

1c) [2]

What is the output of the following R code?

x <- list("a", "b", 1:4)
length(x)

  1. 3

  2. a b 1 2 3 4

  3. 7

  4. a b 1:4

A. 3

1d) [2]

Which of the data type allow non-homogeneous data structure to be stored?

  1. list

  2. vector

  3. matrix

  4. boolean

A. list

1e) [2]

For multivariate methods, to generate a random vector that follows a multivariate normal distribution \(N_d(0,\Sigma)\) with a given covariance matrix \(\Sigma\), one often uses the Cholesky decomposition. What is the role of the Cholesky factor \(L\) when \(\Sigma = L L^\top\)?

  1. \(L\) is the eigenvector matrix

  2. Multiply \(L\) by a standard normal vector gives the desired correlation structure

  3. \(L^{-1}\) is used to whiten the data

  4. None of the above

B. Multiply \(L\) by a standard normal vector gives the desired correlation structure

1f) [2]

In the acceptance–rejection algorithm, the proposal distribution \(g(x)\) and the constant \(k\) should be chosen such that:

  1. \(g(x)\) is complicated to sample from, and \(k\) is as large as possible.

  2. \(g(x)\) is easy to sample from, and \(k\) is as small as possible while satisfying \(f_X(x) \le k\, g(x)\) for all \(x\).

  3. \(g(x)\) closely matches \(f_X(x)\) but \(k\) can be arbitrarily large.

  4. \(g(x)\) is uniform on \([0,1]\), and \(k = 1\) regardless of \(f_X(x)\).

B \(g(x)\) is easy to sample from, and \(k\) is as small as possible while satisfying \(f_X(x) \le k\, g(x)\) for all \(x\).

1g) [2]

What is not a difference between theoretical results and computational reality?

  1. Theoretical results assume exact arithmetic, while computers use finite precision.

  2. Theoretical results may ignore algorithmic complexity, while computation must consider time and memory.

  3. Theoretical results are always affected by rounding error, while computation is exact.

  4. Theoretical models may assume infinite samples, while computation works with finite data.

C. Theoretical results are always affected by rounding error, while computation is exact. (This is false.)

1h) [2]

Let \(Z_1\) and \(Z_2\) be independent standard normal random variables, and denote a Chi Square distribution with degree of freedom \(\nu\) by \(\chi^2_\nu\) . Which of the following statements is correct?

  1. \(Z_1 + Z_2 \sim \chi^2_2\)

  2. \(Z_1^2 + Z_2^2 \sim \chi^2_2\)

  3. \(Z_1 Z_2 \sim \chi^2_2\)

  4. \((Z_1 + Z_2)^2 \sim \chi^2_2\)

B

1i) [2]

Consider estimating the integral \[I = \int_0^1 e^{-x^2}\,dx\] using Monte Carlo integration.

If we generate \(X_1, X_2, \dots, X_n \stackrel{\text{i.i.d.}}{\sim} \text{Uniform}(0,1)\), which of the following provides a consistent estimator of \(I\)?

  1. \(\displaystyle \frac{1}{n} \sum_{i=1}^n X_i^2\)

  2. \(\displaystyle \frac{1}{n} \sum_{i=1}^n e^{-X_i^2}\)

  3. \(\displaystyle \frac{1}{n} \sum_{i=1}^n e^{X_i^2}\)

  4. \(\displaystyle \frac{1}{n} \sum_{i=1}^n e^{-X_i}\)

B

Question 2: Conceptual [20]

2a) [4]

In your own words, explain why statistical computing is important. {2–3 sentences}

Any reasonable answers are fine.

2b) [6]

Identify three main reasons why computational results may differ from theoretical results. {1–3 sentences each}

Any reasonable answers are fine.

2c) [6]

Let \(\Sigma\in\mathbb{R}^{r\times r}\) be a covariance matrix. Write its eigendecomposition and describe the dimensions and properties of the eigenvector and eigenvalue matrices. Explain what can be said about the signs of the eigenvalues.

A covariance matrix is symmetric and positive semidefinite, so

\[ \Sigma=Q\Lambda Q^\top. \]

  • \(Q=[q_1,\ldots,q_r]\in\mathbb{R}^{r\times r}\) contains an orthonormal set of eigenvectors. Thus \(Q^\top Q=QQ^\top=I_r\) and \(Q^{-1}=Q^\top\).
  • \(\Lambda=\operatorname{diag}(\lambda_1,\ldots,\lambda_r)\in\mathbb{R}^{r\times r}\) contains the eigenvalues.
  • All eigenvalues are nonnegative. They may be ordered as \(\lambda_1\geq\cdots\geq\lambda_r\geq0\). Zero eigenvalues are allowed; all are strictly positive when \(\Sigma\) is positive definite.

2d) [4]

Let \(X_1,X_2,\ldots\) be i.i.d. random variables with \(\mathbb{E}|X_1|<\infty\) and \(\mathbb{E}[X_1]=\mu\). For the estimator

\[ \widehat\mu_n=\overline X_n=\frac{1}{n}\sum_{i=1}^n X_i, \]

state its limit and a mode of convergence guaranteed by these assumptions. Name the theorem that justifies your answer and state whether convergence in probability also holds.

By the strong law of large numbers,

\[ \overline X_n\xrightarrow{\mathrm{a.s.}}\mu. \]

Almost-sure convergence implies convergence in probability, so \(\overline X_n\xrightarrow{p}\mu\) as well. The i.i.d. and finite absolute first-moment assumptions ensure that the stated strong law applies.

Question 3: Calculation [30]

3a) [6]

Suppose \(X\) has the cumulative distribution function

\[ F_X(x)= \begin{cases} 0, & x<\ln(2/3),\\ 3e^x-2, & \ln(2/3)\leq x\leq0,\\ 1, & x>0. \end{cases} \]

Derive the inverse CDF for \(0<u<1\), and write the steps for generating an independent sample from this distribution using uniform random numbers. State the range of the generated values.

  1. Solve \(u=3e^x-2\) for \(x\):

    \[ F_X^{-1}(u)=\ln\left(\frac{u+2}{3}\right),\qquad 0<u<1. \]

  2. Generate independent \(U_1,\ldots,U_n\sim\operatorname{Unif}(0,1)\).

  3. Set \(X_i=\ln((U_i+2)/3)\) for each \(i\).

The support is \([\ln(2/3),0]\), and the generated values lie in its interior with probability one. The CDF is continuous and increasing on that interval, taking values 0 and 1 at its endpoints, so the inverse-CDF construction gives the required distribution.

3b) [8]

Describe a simulated annealing algorithm for minimizing an objective function \(f(x)\). Use a symmetric random-walk proposal and geometric cooling. Specify the initialization, acceptance rule for better and worse proposals, cooling schedule, and a suitable stopping rule.

  1. Choose an initial state \(x_0\), an initial temperature \(T_0>0\), a cooling factor \(0<\alpha<1\), a maximum iteration count \(K\), and a minimum temperature \(0<T_{\min}<T_0\). Keep track of the best state found.

  2. At iteration \(i\), propose \(x'=x_i+\varepsilon_i\), where the increment distribution is symmetric about zero, and compute \(\Delta=f(x')-f(x_i)\).

    • If \(\Delta\leq0\), accept the proposal: \(x_{i+1}=x'\).

    • If \(\Delta>0\), accept it with probability

      \[ p=\exp\left(-\frac{\Delta}{T_i}\right) =\exp\left(-\frac{f(x')-f(x_i)}{T_i}\right). \]

      Draw \(U\sim\operatorname{Unif}(0,1)\) and accept when \(U\leq p\). If rejected, set \(x_{i+1}=x_i\).

  3. Update the best state if the objective improves, and cool using \(T_{i+1}=\alpha T_i\).

  4. Repeat until \(K\) iterations have been performed or the temperature falls below \(T_{\min}\). Return the best state found.

A single rejected proposal gives \(x_{i+1}=x_i\) even when the search is far from an optimum, so zero change in one iteration is not a sufficient stopping rule. This finite run provides a candidate solution; it does not guarantee the global minimum.

3c) [6]

Write the steps for simulating a random variable from the Gaussian mixture

\[ 0.7\,N(\mu_1,\sigma_1^2)+0.3\,N(\mu_2,\sigma_2^2). \]

State any independence assumptions used in your construction.

  1. Independently generate \(X\sim N(\mu_1,\sigma_1^2)\), \(Y\sim N(\mu_2,\sigma_2^2)\), and \(U\sim\operatorname{Unif}(0,1)\).
  2. If \(U\leq0.7\), set \(W=X\); otherwise set \(W=Y\).

Independence of the component selector and the component draws gives

\[ \Pr(W\leq w)=0.7\Pr(X\leq w)+0.3\Pr(Y\leq w), \]

which is the desired mixture CDF. Equivalently, first select the component using \(U\), then generate one normal draw from that component.

3d) [10]

Let \(Z_1,Z_2\) be independent standard normal random variables. Prove that \(W=Z_1^2+Z_2^2\sim\chi^2_2\) using moment generating functions.

You may use the facts that, for \(Z\sim N(0,1)\),

\[ M_{Z^2}(t)=(1-2t)^{-1/2},\qquad t<\tfrac12, \]

and that the MGF of a \(\chi^2_\nu\) random variable is

\[ M_{\chi^2_\nu}(t)=(1-2t)^{-\nu/2},\qquad t<\tfrac12. \]

Explain where independence is used.

Since \(Z_1\) and \(Z_2\) are independent, their squares are independent. For \(t<1/2\),

\[ \begin{aligned} M_W(t) &=\mathbb{E}\left[e^{t(Z_1^2+Z_2^2)}\right]\\ &=\mathbb{E}\left[e^{tZ_1^2}e^{tZ_2^2}\right]\\ &=\mathbb{E}\left[e^{tZ_1^2}\right]\mathbb{E}\left[e^{tZ_2^2}\right]\\ &=(1-2t)^{-1/2}(1-2t)^{-1/2}\\ &=(1-2t)^{-1}=M_{\chi^2_2}(t). \end{aligned} \]

Independence justifies the third equality. Both MGFs exist on an open interval containing zero, so uniqueness of the MGF gives \(Z_1^2+Z_2^2\sim\chi^2_2\).

Question 4: Algorithms [16]

We want to find the root of

\[ f(x)=\ln(2x)-2,\qquad x>0. \]

Use the bracket \([1,10]\) for bisection and the initial value \(x_0=7\) for Newton’s method. Retain full precision in intermediate calculations and report final numerical values to four decimal places.

4a) [8]

Apply the bisection method with \(a_0=1\) and \(b_0=10\). At iteration \(j\), define \(c_j=(a_{j-1}+b_{j-1})/2\), then update the bracket to \([a_j,b_j]\) so that it still contains the root. Report

\[ \boldsymbol\theta_j=(a_j,b_j,c_j,f(a_j),f(b_j)) \]

for \(j=1,2\), and explain each bracket update.

Initially, \(f(1)=\ln2-2\approx-1.3069<0\) and \(f(10)=\ln20-2\approx0.9957>0\). The function is continuous on \([1,10]\), so the bracket contains a root.

Iteration 1: \(c_1=(1+10)/2=5.5\) and \(f(c_1)=\ln11-2\approx0.3979>0\). It has the same sign as \(f(b_0)\), so replace the upper endpoint: \(a_1=1\) and \(b_1=5.5\).

\[ \boxed{\boldsymbol\theta_1\approx(1,\;5.5,\;5.5,\;-1.3069,\;0.3979).} \]

Iteration 2: \(c_2=(1+5.5)/2=3.25\) and \(f(c_2)=\ln6.5-2\approx-0.1282<0\). It has the same sign as \(f(a_1)\), so replace the lower endpoint: \(a_2=3.25\) and \(b_2=5.5\).

\[ \boxed{\boldsymbol\theta_2\approx(3.25,\;5.5,\;3.25,\;-0.1282,\;0.3979).} \]

4b) [8]

For the same root-finding problem, apply Newton’s method with initial value \(x_0=7\). Derive the update formula and report \(\boldsymbol\eta_j=(x_j,f(x_j))\) for \(j=1,2\).

Since \(f'(x)=1/x\), Newton’s update is

\[ x_{j+1}=x_j-\frac{f(x_j)}{f'(x_j)} =x_j[3-\ln(2x_j)]. \]

Starting with \(x_0=7\), the two iterations are

\[ \begin{aligned} x_1&=7[3-\ln14]\approx2.526598693,\\ f(x_1)&\approx-0.379978811,\\ x_2&=x_1[3-\ln(2x_1)]\approx3.486652661,\\ f(x_2)&\approx-0.057910666. \end{aligned} \]

Thus, to four decimal places,

\[ \boxed{\begin{aligned} \boldsymbol\eta_1&=(2.5266,\;-0.3800),\\ \boldsymbol\eta_2&=(3.4867,\;-0.0579). \end{aligned}} \]

The exact root is \(x^\ast=e^2/2\approx3.6945\). The iterations use the unrounded previous value.

Question 5: Convergence [16]

For each sequence, identify its limit \(x_\infty\) and its rate of convergence using the error ratio

\[ \mu=\lim_{n\to\infty}\frac{|x_{n+1}-x_\infty|}{|x_n-x_\infty|}. \]

5a) [6]

For \(x_n=1+(2/5)^n\), find \(x_\infty\) and \(\mu\), and classify the convergence rate. Show the error-ratio calculation.

Since \((2/5)^n\to0\), the limit is \(x_\infty=1\). The error ratio is

\[ \frac{|x_{n+1}-1|}{|x_n-1|} =\frac{(2/5)^{n+1}}{(2/5)^n} =\frac25. \]

Thus \(\mu=2/5=0.4\in(0,1)\), so the sequence converges linearly to 1.

5b) [10]

A sequence converges sublinearly to \(x_\infty\) if it converges to that limit and its error ratio tends to 1. Construct an infinite sequence with this property, state its limit, and verify the error-ratio limit.

Take \(x_n=1/n\) for \(n=1,2,\ldots\). Then \(x_n\to0\), so \(x_\infty=0\), and

\[ \frac{|x_{n+1}-0|}{|x_n-0|} =\frac{1/(n+1)}{1/n} =\frac{n}{n+1}\longrightarrow1. \]

Hence \(\mu=1\) and the convergence is sublinear.