院試過去問 2004年度専門科目数理のバックアップ(No.11)

院試勉強会

http://www.i.u-tokyo.ac.jp/edu/course/mi/admission.shtml
http://www.i.u-tokyo.ac.jp/edu/course/mi/pdf/2004suuri-j.pdf

ところで，この解答を見てる人はどれぐらいいるのでしょうか．．．
解答に対してつっこみなどのコメントを下に残していただければ助かります．

第1問
- (1)確率ベクトルと二重確率行列がを満たすとき，となることを示せ．
  - $\frac{d^2}{dx^2}\log x=-1/x^2<0$ なので， $\log(\sum_{i=1}^n p_i\lambda_i)\ge \sum_{i=1}^n p_i\log\lambda_i$ となることに注意する．
    $\begin{align*}H(\bm{q})&=-\sum_{i=1}^n q_i\log q_i\\&=-\sum_{i=1}^n\sum_{j=1}^n p_ja_{ji}\log(\sum_{k=1}^n p_ka_{ki})\\&\ge -\sum_{j=1}^n p_j\log(\sum_{k=1}^n\sum_{i=1}^n p_k a_{ki}a_{ji})\\&=-\sum_{j=1}^n p_j\log(\sum_{i=1}^n p_j a_{ji}a_{ji})\\&\ge -\sum_{j=1}^n p_j\log(p_j)=H(\bm{p}).\end{align*}$
- (2)確率ベクトルと二重確率行列がを満たすとき，に対してとなることを示せ．
  - 一般性を失わず $p_1\ge p_2\ge \dots\ge p_n,\ q_1\ge q_2\ge \dots\ge q_n$ としてよい．このとき，
    $\begin{align*}\sigma_{k}(\bm{q})&=\sum_{i=1}^k q_i\\&=\sum_{i=1}^k \sum_{j=1}^n p_j a_{ji}\\&=\sum_{j=1}^n p_j (\sum_{i=1}^k a_{ji})\\&\le \sum_{j=1}^k p_j=\sigma_k(\bm{p}).\end{align*}$
    （最後の行はグリーディーにとったものである．）
- (3)確率ベクトルがに対してを満たすとき，である二重確率行列が存在することを示せ．
  - 帰納法で証明する．のときは成立は明らか．よって，のときの成立を仮定してのときの成立を示せばよい．一般性を失わず $p_1\ge p_2\ge \dots\ge p_{m+1},\ q_1\ge q_2\ge \dots\ge q_{m+1}$ としてよく，また $q_1=a_{1,1}p_1+a_{1,m+1}p_{m+1}, a_{1,1}+a_{1,m+1}=1$ , $a_{1,2}=a_{1,3}=\dots=a_{1,m}=0$ とおく．ここで， $\bm{p}'=\{p_2+(1-a_{1,1}p_1),p_3,\dots,p_{m},(1-a_{1,m+1})p_{m+1}\},\ \bm{q}'=\{p_2,p_3,\dots,p_{m+1}\}$ について帰納法の仮定より $\frac{1}{1-q_1}\bm{q}'=\frac{1}{1-q_1}\bm{p}A'$ なる二重確率行列が存在する．この $A'=(a'_{ij})$ を使い適当に変形して正規化すれば，は $\bm{q}=\bm{p}A$ を満たす二重確率行列となる．
    よって帰納法により題意は示された．

第2問
- 実次元空間 $\mathbb{R}^n$ において，あるベクトル $\bm{c}$ とある正定値対称行列によって $\{\bm{x}|(\bm{x}-\bm{c})^{\top}A(\bm{x}-\bm{c})\le 1\}$ と表される図形を楕円体といい， $\bm{c}$ をその中心と呼ぶ．
  原点を中心とした楕円体を原点を通る超平面で切断して二つに分け，その一方をとする．を含む体積最小の楕円体の体積 $\mathrm{vol}(F)$ との体積 $\mathrm{vol}(E)$ の比を $\rho=\mathrm{vol}(F)/\mathrm{vol}(E)$ とおく．
(1)が

の場合に，の中心との値を求めよ．
- $F$ は軸対称。を含む2次元平面での切断面上で考えれば十分、
  この面への $K$ の射影は、単位円の右半分。
  $F$ の射影はを通りを中心とする楕円となる．
  これより，の射影を $\frac{x_1^2}{a^2}+\frac{(x_n-c)^2}{b^2}\le 1$ とすれば，
  $\begin{align*}\frac{1}{a^2}+\frac{c^2}{b^2}&=1\\\frac{(1-c)^2}{b^2}&=1\end{align*}$
  これを解いて， $a^2=\frac{b^2}{2b-1}$ .
  また， $\rho=a^{n-1}b$ が最小となるのは $a^{2(n-1)}b^2=b^2\left(\frac{b^2}{2b-1}\right)^{n-1}$ が最小となるを求めればよい．
  で微分すると， $\left(\frac{b^2}{2b-1}\right)^{n-1}\frac{2}{2b-1}((n+1)b-n)$ より， $b=\frac{n}{n+1}$ で最小．
  以上より，
  $\begin{align*}\rho=a^{n-1}b=\frac{n}{n+1}\cdot\left(\frac{n^2}{n^2-1}\right)^{\frac{n-1}{2}}.\end{align*}$
  中心の座標は $\begin{pmatrix}0&0&\dots&0&c\end{pmatrix}=\begin{pmatrix}0&\dots&0&\frac{1}{n+1}\end{pmatrix}$

(2)上で求めたに関して，のときが0に収束することを示し，さらに，その収束の速さを論ぜよ．
- $\lim_{n\to\infty}\rho$ は，
  $\begin{align*}\lim_{n\to\infty}\rho&=\frac{n}{n+1}\left(\frac{n^2}{n^2-1}\right)^{(n-1)/2}\\&=\lim_{n\to\infty}\left(1-\frac{1}{n+1}\right)^{(n+1)/2}\left(1-\frac{1}{n-1}\right)^{(n-1)/2}\\&\to e^{1/2}e^{-1/2}=1\end{align*}$
  となるので， $\lim_{n\to\infty}\log\rho\to 0$ ．
  $(n-1)\log\left(1+\frac{1}{n-1}\right)\simeq 1-\frac{1}{2}\frac{1}{n-1}+O(1/n^2)$
  $(n+1)\log\left(1-\frac{1}{n+1}\right)\simeq -1-\frac{1}{2}\frac{1}{n+1}+O(1/n^2)$
  これより，
  $\begin{align*}\log\rho&=\frac{(n-1)}{2}\log\left(1+\frac{1}{n-1}\right)+\frac{(n+1)}{2}\log\left(1+\frac{1}{n+1}\right)\\&=-\frac{1}{4}\frac{n}{n^2-1}+O(1/n^2)\end{align*}$
  となるので，収束の速さは．

(3)一般の場合のに対して，がに依らず，だけの関数であることを説明せよ．
- 適当な1次変換をすることで原点を中心とした楕円体は原点を中心とした球に変換できる．また，1次変換によって体積の比は変わらないので $\rho$ はだけの関数になる．

第3問
- (1)平面上に平行な直線が等間隔に引かれている．隣り合う2直線の間隔を1とする．この平面状に長さ1の針をランダムに投げる．針が直線群と交わる確率を求めよ．
  - すぐ下の直線から針の重心までの距離がで直線となす角が $\theta$ であるとする．すると面積を考えて，
    $\begin{align*}\frac{\int_0^{\pi/2}\frac{\sin\theta}{2}d\theta}{1/2\cdot\pi/2}&=\frac{1/2}{\pi/4}=\frac{2}{\pi}.\end{align*}$
- (2)針を回投げ,針が直線群と交わった回数を記録する実験を行う．の分散を求めよ．の従う分布は，のときどのような分布に収束するか．
  - 2項分布なので，の分散は．よって，の分散は．また，中心極限定理より $\sqrt{n}\left(\frac{X}{n}-p\right)$ の従う分布は平均，分散の正規分布になる．
- (3)1辺の長さが1の正角形を平面状にランダムに投げる．正角形の周と直線群との交点の個数の期待値を求めよ．
  - 期待値の線型性より， $Y=m*\frac{2}{\pi}=\frac{2m}{\pi}$ ．

第5問
一般に，同じ大きさの正方行列に対して，記号は，行列を表すものとする．同じ大きさの実対称行列に関する微分方程式の初期値問題

を考える．
- (1)任意のに対してであることを示せ．
  - $(U(t)BU(t)^{\top})^{\top}=(U(t)BU(t)^{\top})$ なので，であり，が実対称行列のとき $[P,Q]+[P,Q]^{\top}=(PQ-QP)+(Q^{\top}P^{\top}-P^{\top}Q^{\top}=0)$ であることに注意して，
    $\begin{align*}\frac{d}{dt}U(t)^{\top}U(t)&=\frac{dU(t)^{\top}}{dt}U(t)+U(t)^{\top}\frac{dU(t)}{dt}\\&=U(t)^{\top}([A,U(t)BU(t)^{\top}]^{\top}+[A,U(t)BU(t)^{\top}])U(t)\\&=0\end{align*}$
    なので，任意のに対してである．
- (2)行列は，任意のに対して，
  
  を満たすことを示せ．
  - $\mathrm{Tr}(AB)=\mathrm{Tr}(BA)$ なので，
    $\newcommand{\Tr}{\mathrm{Tr}}\begin{align*}\frac{d}{dt}\Tr(AX(t))&=\Tr\left(A\frac{dX(t)}{dt}\right)\\&=\Tr\left(A\frac{dU(t)}{dt}BU(t)^{\top}+AU(t)B\frac{dU(t)^{\top}}{dt}\right)\\&=\Tr\left(A[U(t),X(t)]X(t)+AX(t)^{\top}[A,X(t)]^{\top}\right)\\&=\Tr\left([A,X(t)]X(t)A-[A,X(t)]AX(t)\right)\\&=\Tr\left([A,X(t)](X(t)A-AX(t))\right)\\&=\Tr\left([A,X(t)](-[A,X(t)])\right)\\&=\Tr\left([A,X(t)][A,X(t)]^{\top}\right)\end{align*}$
- (3)任意のに対して
  $\begin{align*}\frac{d}{dt}\mathrm{Tr}(AX(t))\ge 0\end{align*}$
  であり， $t\to\infty$ の極限において
  $\begin{align*}\frac{d}{dt}\mathrm{Tr}(AX(t))\to 0\end{align*}$
  となることを示せ．
- (4)が相異なる実数を対角要素とする対角行列であるとき，の極限においてがの固有値を対角成分とする対角行列に収束することを示せ．
  - $\frac{d}{dt}\mathrm{Tr}(AX(t))=\mathrm{Tr}([A,X(t)][A,X(t)]^{\top})\to 0$ であり，
    $\begin{align*}\mathrm{Tr}([A,X(t)][A,X(t)]^{\top})&=(a_{ii}-a_{jj})^2x_{ij}^2\to 0.\end{align*}$
    ここで，の対角成分は全て異なるので，は対角行列に収束する．
    または(1)より直交行列なので，の固有値はの固有値に等しい．よって，はの固有値を対角成分とする対角行列に収束する．

第5問
円周上に個の点があるとする()．その中の一つの点から初めて時計回りに順にとする．円の中心を原点とする正規直交座標系における各点の座標がいずれも有理数であって，これらが与えられているものとする．次のそれぞれの問題に大して，に関して線型時間のアルゴリズムを設計せよ．
- (1)の中に直径の両端点となる2点が存在するかどうかを判定する問題．
  - ,flag=FALSEと初期化する．
    または $j\ge N$ ならば終了しflagを返す．
    角との外積が正のときはをインクリメント，負のときはをインクリメントし，0のときは flag=TRUEとし，をに更新する．
    毎回のどちらかはインクリメントされるので時間計算量は．
- (2)の中の4点を頂点とする長方形が存在するかどうかを判定する問題．
  - (1)のアルゴリズムを用いれば，円の直径の両端点となる2点の集合が分かるので，その集合の大きさが2以上であれば存在する．線型時間．
- (3)の中の4点を頂点とする長方形の中で面積が最大となるものを求める問題．
  - (1)のアルゴリズムを走らせて，円の直径の両端点となる2点の集合 $V=[V_0=(F_0,T_0),\dots,V_{n-1}=(F_{n-1},T_{n-1})]$ をもとめる． $i=0,j=0,\mathrm{max}=0$ と初期化する． $F_iOF_j\le \pi/4< F_iOF_{(j+1)\%n}$ となるまでをインクリメントして， $\mathrm{max}$ を現在の値とを使ったときの長方形の面積の値と $V_{i},V_{(j+1)\%n}$ を使ったときのそれの最大値に更新する．ならをインクリメントする．
    というアルゴリズムを用いればよい．