2014

Problem 1

A real square matrix $\mathbf{M}$ is said to be symmetric if it satisfies the condition $\mathbf{M}={\mathbf{M}}^{\mathbf{T}}$, where ${\mathbf{M}}^{\mathbf{T}}$ denotes the transpose of $\mathbf{M}$. Answer the following questions.

1. Find all the eigenvalues and their corresponding eigenvectors of the symmetric matrix $\mathbf{A}$ given as follows.

$$\mathbf{A}=\left(\begin{array}{ccc}1& -1& 0\\ -1& 1& -1\\ 0& -1& 1\end{array}\right)$$

2. Prove that if a real square matrix $\mathbf{M}$ is symmetric, then all of its eigenvalues are real.

3. Even if all the eigenvalues of a real square matrix $\mathbf{M}$ are real, $\mathbf{M}$ is not necessarily symmetric. Provide a concrete example of such a matrix $\mathbf{M}$.

4. Let $\mathbf{u}=\left(\begin{array}{c}x\\ y\\ z\end{array}\right)$ be a non-zero three-dimensional real vector. For the symmetric matrix $\mathbf{A}$ defined in question (1), let us define the function $f(x,y,z)$ as follows.

$$f(x,y,z)=\frac{{\mathbf{u}}^{\mathbf{T}}\mathbf{Au}}{{\mathbf{u}}^{\mathbf{T}}\mathbf{u}}$$

Here, ${\mathbf{u}}^{\mathbf{T}}$ denotes the transpose of $\mathbf{u}$. Moreover, the function $g(x,y,z)$ is defined as follows.

$$g(x,y,z)=\frac{xy+yz}{x^2+y^2+z^2}$$

Show that the following equation holds.

$$f(x,y,z)=1-2g(x,y,z)$$

5. Using eigenvalue decomposition of the symmetric matrix $\mathbf{A}$ defined in question (1), show that the following inequality holds for the function $g(x,y,z)$ defined in question (4).

$$-\frac{1}{\sqrt{2}}\le g(x,y,z)\le \frac{1}{\sqrt{2}}$$

---

一个实方阵 $\mathbf{M}$ 如果满足条件 $\mathbf{M}={\mathbf{M}}^{\mathbf{T}}$，则称其为对称矩阵，其中 ${\mathbf{M}}^{\mathbf{T}}$ 表示 $\mathbf{M}$ 的转置。回答以下问题。

1. 求出如下对称矩阵 $\mathbf{A}$ 的所有特征值及其对应的特征向量。

$$\mathbf{A}=\left(\begin{array}{ccc}1& -1& 0\\ -1& 1& -1\\ 0& -1& 1\end{array}\right)$$

2. 证明如果一个实方阵 $\mathbf{M}$ 是对称的，那么它的所有特征值都是实数。

3. 即使一个实方阵 $\mathbf{M}$ 的所有特征值都是实数，$\mathbf{M}$ 也不一定是对称的。提供一个这样的矩阵 $\mathbf{M}$ 的具体例子。

4. 令 $\mathbf{u}=\left(\begin{array}{c}x\\ y\\ z\end{array}\right)$ 为一个非零的三维实向量。对于问题 (1) 中定义的对称矩阵 $\mathbf{A}$，定义函数 $f(x,y,z)$ 如下。

$$f(x,y,z)=\frac{{\mathbf{u}}^{\mathbf{T}}\mathbf{Au}}{{\mathbf{u}}^{\mathbf{T}}\mathbf{u}}$$

其中 ${\mathbf{u}}^{\mathbf{T}}$ 表示 $\mathbf{u}$ 的转置。此外，函数 $g(x,y,z)$ 定义如下。

$$g(x,y,z)=\frac{xy+yz}{x^2+y^2+z^2}$$

证明下式成立。

$$f(x,y,z)=1-2g(x,y,z)$$

5. 使用问题 (1) 中定义的对称矩阵 $\mathbf{A}$ 的特征值分解，证明问题 (4) 中定义的函数 $g(x,y,z)$ 满足以下不等式。

$$-\frac{1}{\sqrt{2}}\le g(x,y,z)\le \frac{1}{\sqrt{2}}$$

---

Problem 2

For real functions $f(x)$ and $g(x)$ defined on $[-1,1]$, let

$$(f,g)={\int }_{-1}^{1}f(x)g(x)\mathrm{d}x.$$

Answer the following questions.

1. Calculate $(q_0,q_1)$, $(q_0,q_2)$, $(q_1,q_2)$, $(q_0,q_0)$, $(q_1,q_1)$, and $(q_2,q_2)$ for polynomials defined by

$$q_0(x)=1,q_1(x)=x,q_2(x)=3x^2-1.$$

You may use the fact that ${\int }_{-1}^{1}h(x)\mathrm{d}x=0$ holds for any odd function $h(x)$.

2. Let $p_k(x)$ be a polynomial of degree $k$ with respect to $x$ (with the coefficient of $x^k$ not being 0), and consider a series of polynomial functions $p_0(x),p_1(x),\dots$. In what follows, we say a set of $N$ functions $\{p_0(x),p_1(x),\dots ,p_{N-1}(x)\}$ satisfies the orthonormal condition when

$$(p_i,p_j)=\{\begin{array}{ll}1& (i=j)\\ 0& (i\ne j)\end{array}$$

holds for any integers $i$ and $j$ in $[0,N-1]$.

(2-1) Using $q_0(x)$, $q_1(x)$, and $q_2(x)$ defined in question (1), find a set of functions $\{p_0(x),p_1(x),p_2(x)\}$ satisfying the orthonormal condition.

(2-2) Find a function $p_3(x)$ so that a set of functions $\{p_0(x),p_1(x),p_2(x),p_3(x)\}$ satisfies the orthonormal condition, where $p_0(x)$, $p_1(x)$, and $p_2(x)$ are the functions derived in question (2-1).

3. Suppose that a set of functions $\{p_0(x),p_1(x),\dots ,p_{N-1}(x)\}$ satisfies the orthonormal condition. Then, in a manner similar to question (2-2), a function $p_N(x)$ can be found such that the set of functions $\{p_0(x),p_1(x),\dots ,p_N(x)\}$ satisfies the orthonormal condition. Show that $p_N(x)$ is unique except the sign, following the steps below.

   (3-1) Generally, a polynomial $f_N(x)$ of degree $N$ can be written as

$$f_N(x)=\sum _{k=0}^N{c}_k{p}_k(x).$$

Express the coefficients $c_k(k=0,\dots ,N)$ with $p_0(x),p_1(x),\dots ,p_N(x)$, and $f_N(x)$.

(3-2) Suppose that there exists a polynomial function ${\tilde{p}}_N(x)$ of degree $N$ different from $p_N(x)$ such that the set of functions $\{p_0(x),p_1(x),\dots ,p_{N-1}(x),{\tilde{p}}_N(x)\}$ also satisfies the orthonormal condition. Then prove that ${\tilde{p}}_N(x)=-p_N(x)$ by considering the case $f_N(x)={\tilde{p}}_N(x)$ in question (3-1).

---

对于定义在 $[-1,1]$ 上的实函数 $f(x)$ 和 $g(x)$，定义

$$(f,g)={\int }_{-1}^{1}f(x)g(x)\mathrm{d}x。$$

回答以下问题。

1. 计算多项式定义下的 $(q_0,q_1)$、$(q_0,q_2)$、$(q_1,q_2)$、$(q_0,q_0)$、$(q_1,q_1)$ 和 $(q_2,q_2)$

$$q_0(x)=1,q_1(x)=x,q_2(x)=3x^2-1.$$

可以使用以下事实：${\int }_{-1}^{1}h(x)\mathrm{d}x=0$ 对任何奇函数 $h(x)$ 都成立。

2. 令 $p_k(x)$ 为关于 $x$ 的 $k$ 次多项式（$x^k$ 的系数不为 0），并考虑一系列多项式函数 $p_0(x),p_1(x),\dots$。下文中，当满足以下条件时，我们说 $N$ 个函数 $\{p_0(x),p_1(x),\dots ,p_{N-1}(x)\}$ 满足正交归一化条件。

$$(p_i,p_j)=\{\begin{array}{ll}1& (i=j)\\ 0& (i\ne j)\end{array}$$

条件对任何整数 $i$ 和 $j$ 在 $[0,N-1]$ 内成立。

(2-1) 使用问题 (1) 中定义的 $q_0(x)$、$q_1(x)$ 和 $q_2(x)$，找到满足正交归一化条件的函数集 $\{p_0(x),p_1(x),p_2(x)\}$。

(2-2) 找到一个函数 $p_3(x)$，使得函数集 $\{p_0(x),p_1(x),p_2(x),p_3(x)\}$ 满足正交归一化条件，其中 $p_0(x)$、$p_1(x)$ 和 $p_2(x)$ 为问题 (2-1) 中导出的函数。

3. 假设函数集 $\{p_0(x),p_1(x),\dots ,p_{N-1}(x)\}$ 满足正交归一化条件。然后，以类似于问题 (2-2) 的方式，可以找到一个函数 $p_N(x)$，使得函数集 $\{p_0(x),p_1(x),\dots ,p_N(x)\}$ 满足正交归一化条件。按以下步骤证明 $p_N(x)$ 是唯一的，除了符号外。

   (3-1) 通常，一个 $N$ 次多项式 $f_N(x)$ 可以表示为

$$f_N(x)=\sum _{k=0}^N{c}_k{p}_k(x)。$$

用 $p_0(x)$、$p_1(x)$、$\dots$、$p_N(x)$ 和 $f_N(x)$ 表示系数 $c_k(k=0,\dots ,N)$。

(3-2) 假设存在一个与 $p_N(x)$ 不同的 $N$ 次多项式函数 ${\tilde{p}}_N(x)$，使得函数集 $\{p_0(x),p_1(x),\dots ,p_{N-1}(x),{\tilde{p}}_N(x)\}$ 也满足正交归一化条件。通过考虑问题 (3-1) 中的 $f_N(x)={\tilde{p}}_N(x)$，证明 ${\tilde{p}}_N(x)=-p_N(x)$。

---

Problem 3

Let $x_0,x_1,x_2,\dots$ be a sequence of independent random variables. Each $x_i(i=0,1,2,\dots )$ takes value 1 with probability $p$ and value 0 with probability $1-p$. Answer the following questions.

1. With regards to the sequence of random variables $x_0,x_1,x_2,\dots$, answer the following questions.

   1.1 Calculate the variance of $x_i$, and obtain the probability that $x_0=x_1=1$.

   1.2 Let $k(k\ge 0)$ be the smallest integer such that $x_k=x_{k+1}$. For example, if $x_0,x_1,x_2,\dots$ is $1,0,0,1,1,0,0,\dots$, then $k=1$ and $x_k=0$. Obtain the probability that $x_k=1$.

2. A sequence of random variables $y_0,y_1,y_2,\dots$ is defined using $x_0,x_1,x_2,\dots$ as follows.

   $$y_0=1$$ $$y_{i+1}=y_i+\alpha (x_i-y_i)(i=0,1,2,\dots )$$

   Assume $0<\alpha <1$, and answer the following questions.

   2.1 Show that $y_n=(1-\alpha {)}^n+{\sum }_{i=0}^{n-1}(1-\alpha {)}^{n-i-1}\alpha x_i(n=1,2,\dots )$.

   2.2 Obtain the expected value $E_n$ and the variance $V_n$ of $y_n$.

   2.3 Let $E_{\infty }={\lim }_{n\to \infty }{E}_n$ and $V_{\infty }={\lim }_{n\to \infty }{V}_n$. Assuming $\frac{1}{2}<p<\frac{3}{4}$, obtain the maximum value of $\alpha$ that satisfies the condition $E_{\infty }-\sqrt{V_{\infty }}\ge \frac{1}{2}$.

3. A sequence of random variables $z_0,z_1,z_2,\dots$ is defined using $x_0,x_1,x_2,\dots$ as follows. If $x_j,x_{j+1}$ is the $i$-th pair of adjacent variables in $x_0,x_1,x_2,\dots$ such that $x_j=x_{j+1}$, then $z_i$ is defined by $z_i=x_j$. The index $i$ starts with 0, so if $x_j=x_{j+1}$ is the first such pair, then $z_0=x_j$. For example, if $x_0,x_1,x_2,\dots$ is $1,0,0,1,0,0,1,1,1,0,0,\dots$, then $z_0=0,z_1=1,z_2=1,z_3=0,\dots$.

   Let $q_i$ be the probability that $z_i=1$. Obtain ${\lim }_{i\to \infty }{q}_i$.

---

令 $x_0,x_1,x_2,\dots$ 是一个独立随机变量序列。每个 $x_i(i=0,1,2,\dots )$ 以概率 $p$ 取值 1，以概率 $1-p$ 取值 0。回答以下问题。

1. 关于随机变量序列 $x_0,x_1,x_2,\dots$，回答以下问题。

   1. 计算 $x_i$ 的方差，并求出 $x_0=x_1=1$ 的概率。

   2. 设 $k(k\ge 0)$ 是使得 $x_k=x_{k+1}$ 的最小整数。例如，如果 $x_0,x_1,x_2,\dots$ 是 $1,0,0,1,1,0,0,\dots$，那么 $k=1$ 并且 $x_k=0$。求 $x_k=1$ 的概率。

2. 使用 $x_0,x_1,x_2,\dots$ 定义随机变量序列 $y_0,y_1,y_2,\dots$ 如下。

   $$y_0=1$$ $$y_{i+1}=y_i+\alpha (x_i-y_i)(i=0,1,2,\dots )$$

   假设 $0<\alpha <1$，回答以下问题。

   1. 证明 $y_n=(1-\alpha {)}^n+{\sum }_{i=0}^{n-1}(1-\alpha {)}^{n-i-1}\alpha x_i(n=1,2,\dots )$。

   2. 求 $y_n$ 的期望 $E_n$ 和方差 $V_n$。

   3. 令 $E_{\infty }={\lim }_{n\to \infty }{E}_n$ 和 $V_{\infty }={\lim }_{n\to \infty }{V}_n$。假设 $\frac{1}{2}<p<\frac{3}{4}$，求满足条件 $E_{\infty }-\sqrt{V_{\infty }}\ge \frac{1}{2}$ 的 $\alpha$ 的最大值。

3. 使用 $x_0,x_1,x_2,\dots$ 定义随机变量序列 $z_0,z_1,z_2,\dots$ 如下。如果 $x_j,x_{j+1}$ 是 $x_0,x_1,x_2,\dots$ 中的第 $i$ 对相邻变量，使得 $x_j=x_{j+1}$，则 $z_i$ 定义为 $z_i=x_j$。索引 $i$ 从 0 开始，因此如果 $x_j=x_{j+1}$ 是第一个这样的对，则 $z_0=x_j$。例如，如果 $x_0,x_1,x_2,\dots$ 是 $1,0,0,1,0,0,1,1,1,0,0,\dots$，则 $z_0=0,z_1=1,z_2=1,z_3=0,\dots$。

   设 $q_i$ 是 $z_i=1$ 的概率。求 ${\lim }_{i\to \infty }{q}_i$。