[[院試勉強会]] 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)確率ベクトル&imgtex($\bm{p},\bm{q}$);と二重確率行列&imgtex($A$);が&imgtex($\bm{q}=\bm{p}A$);を満たすとき, &imgtex($H(\bm{q})\ge H(\bm{p})$);となることを示せ. ---&imgtex($\frac{d^2}{dx^2}\log x=-1/x^2<0$);なので,&imgtex($\log(\sum_{i=1}^n p_i\lambda_i)\ge \sum_{i=1}^n p_i\log\lambda_i$);となることに注意する.~ &imgtex(\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*}); ---[別解]&imgtex($g(x)=-x\log(x),0<x<1$);とすると、凸関数であるから~ &imgtex(\[ g\left(\sum_{i}a_ix_i\right)\geq \sum_{i}a_ig(x_i) , \sum_i a_i = 1,a_i>0\]);~ これを利用して~ &imgtex(\begin{align*} H(\bm q)& = \sum_{j=1}^ng(q_j) \\ & = \sum_{j=1}^n g\left(\sum_{i=1}^na_{ij}p_j\right) \\ & \geq \sum_{j=1}^n \sum_{i=1}^n a_{ij}g(p_j)\\ & = \sum_{j=1}^ng(p_j) = H(\bm p)\end{align*}); --(2)確率ベクトル&imgtex($\bm{p},\bm{q}$);と二重確率行列&imgtex($A$); が&imgtex($\bm{q}=\bm{p}A$);を満たすとき, &imgtex($k=1,2,\dots,n$);に対して&imgtex($\sigma_k(\bm{q})\le \sigma_k(\bm{p})$);となることを示せ. ---一般性を失わず&imgtex($p_1\ge p_2\ge \dots\ge p_n,\ q_1\ge q_2\ge \dots\ge q_n$);としてよい.このとき,~ &imgtex(\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)確率ベクトル&imgtex($\bm{p},\bm{q}$);が&imgtex($k=1,2,\dots,n$);に対して &imgtex($\sigma_k(\bm{q})\le \sigma_k\bm{p}$);を満たすとき, &imgtex($\bm{q}=\bm{p}A$);である二重確率行列&imgtex($A$);が存在することを示せ. ---帰納法で証明する. &imgtex($n=1$);のときは成立は明らか. よって,&imgtex($n=m$);のときの成立を仮定して&imgtex($n=m+1$);のときの成立を示せばよい. 一般性を失わず&imgtex($p_1\ge p_2\ge \dots\ge p_{m+1},\ q_1\ge q_2\ge \dots\ge q_{m+1}$);としてよく,また&imgtex($q_1=a_{1,1}p_1+a_{1,m+1}p_{m+1}, a_{1,1}+a_{1,m+1}=1$);,&imgtex($a_{1,2}=a_{1,3}=\dots=a_{1,m}=0$);とおく. ここで,&imgtex($\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}\}$);について帰納法の仮定より&imgtex($\frac{1}{1-q_1}\bm{q}'=\frac{1}{1-q_1}\bm{p}A'$);なる二重確率行列が存在する. この&imgtex($A'=(a'_{ij})$);を使い適当に変形して正規化すれば, &imgtex($A$);は&imgtex($\bm{q}=\bm{p}A$);を満たす二重確率行列となる.~ よって帰納法により題意は示された. ---[別解] &imgtex($A,B$);が二重確率行列であるとき、&IMGTEX($AB$);も二重確率行列であることに注目。~ &imgtex($\sigma_k(\bm q)\leq \sigma_k(\bm p), k = 1,2,\ldots,n$);を満たす&imgtex($\bm q,\bm p$);に対して、 &imgtex($\bm q'=(q_2,q_3,\ldots,q_n),\bm p' = \left((\bm p A_n)_2,(\bm p A_n)_3,\ldots,(\bm p A_n)_n\right)$);としたとき、 &imgtex(\[ q_1 = \left(\bm p A_n\right)_1,\ \sigma_k(\bm q')\leq \sigma_k(\bm p'),\ k = 1,2,3,\ldots,n-1,\ \sum_{i=1}^{n-1}q'_i = \sum_{i=1}^{n-1}p'_i\]);~ を満たす二重確率行列&imgtex($A_n$);を見つけることができれば、これを繰り返し、得られた二重確率行列&imgtex($A_n,A_{n-1},\ldots,A_2$);を用いて、 &imgtex(\[ A=A_n\begin{pmatrix} 1&0&\cdots&0\\ 0& & & &\\ \vdots& &A_{n-1}& \\ 0 & & & \\ \end{pmatrix}\cdots\begin{pmatrix} I_{n-3}&O\\ O&A_3\\\end{pmatrix}\begin{pmatrix} I_{n-2}&O\\ O&A_{2}\\\end{pmatrix}\]);~ と目的の&imgtex($\bm q=\bm p A$);なる二重確率行列&imgtex($A$);が得られる。 従って、示すべきは&imgtex($A_n$);の存在。 一般性を失うことなく&imgtex($q_1\geq q_2\geq \ldots\geq q_n, p_1\geq p_2\geq\ldots\geq p_n$);とできる。 ここで、&imgtex($\sigma_k(\bm q)\leq \sigma_k(\bm p)$);であるから、 &imgtex($p_n\leq q_1 \leq p_1$);が成立。そこで、&imgtex($p_k\leq q_1 \leq p_{k-1}$);なる&imgtex($k$);をとれば、ある&imgtex($0\leq t \leq 1$);が存在して、&imgtex($q_1 = tp_1 + (1-t)p_k$);であるから、 &imgtex(\[ A_n= \begin{pmatrix} t&&1-t\\ &\ddots&&&\\ 1-t&&t\\ &&&\ddots\\ \end{pmatrix}\]);~ とすればよい。(&imgtex($(A_n)_{11}=(A_n)_{kk}=t$);で他の対角要素は&imgtex($1$);である。) 実際、&imgtex($p_1\geq p_2\geq \ldots \geq p_{k-1}\geq q_1 \geq q_2 \geq \ldots \geq q_n$);であるから、~ &imgtex(\[ \sigma_m(\bm q ')\leq \sigma_m(\bm p'),\ k = 1,2,\ldots,k-2\]);~ また、&imgtex($m=k-1,k,\ldots,n-1$);については~ &imgtex(\[ \sum_{i=1}^m p'_i = \sum_{i=2}^{m-1}p_i + p_1 - q_1 = \sum_{i=1}^{m-1}p_i - q_1 \geq \sum_{i=1}^{m-1}q_i - q_1\]);~ であるから、&imgtex($\sigma_m(\bm q')\leq \sigma_m(\bm p')$);がわかる。 ---- -第2問~ --実&imgtex($n$);次元空間&imgtex($\mathbb{R}^n$);において, あるベクトル&imgtex($\bm{c}$);とある正定値対称行列&imgtex($A$);によって &imgtex($\{\bm{x}|(\bm{x}-\bm{c})^{\top}A(\bm{x}-\bm{c})\le 1\}$);と表される図形を楕円体といい, &imgtex($\bm{c}$);をその中心と呼ぶ.~ 原点を中心とした楕円体&imgtex($E$);を原点を通る超平面&imgtex($H$);で切断して二つに分け,その一方を&imgtex($K$);とする. &imgtex($K$);を含む体積最小の楕円体&imgtex($F$);の体積&imgtex($\mathrm{vol}(F)$);と&imgtex($E$);の体積&imgtex($\mathrm{vol}(E)$);の比を &imgtex($\rho=\mathrm{vol}(F)/\mathrm{vol}(E)$);とおく. -(1)&imgtex($E,H,K$);が~ &imgtex(\begin{align*}E&=\{\bm{x}|\sum_{i=1}^n x_i^2\le 1\},\\H&=\{\bm{x}|x_n=0\}\\K&=\{\bm{x}|\sum_{i=1}^n x_i^2\le 1, x_n\ge 0\}\end{align*});~ の場合に,&imgtex($F$);の中心と&imgtex($\rho$);の値を求めよ. --- &imgtex(\(F\));は&imgtex(\[x_n\]);軸対称。&imgtex(\[x_n\]);を含む2次元平面での切断面上で考えれば十分、~ この面への&imgtex(\(K\));の射影は、単位円の右半分。~ &imgtex(\(F\));の射影は&imgtex($(1,0),(0,1)$);を通り&imgtex($(c,0)$);を中心とする楕円となる.~ //&imgtex(\(F\));の射影はそれを含む面積最小の楕円となる。~ //&imgtex(\[(1,0),(0,1)\]);を通り、&imgtex(\[(r,0)\]);を中心とする楕円の面積は~ //&imgtex(\[\pi\frac{(1-r)^2}{\sqrt{1-2r}}\]);。これは&imgtex(\[r=\frac{1}{3}\]);で最小。~ //&imgtex(\[\left(\frac{x-r}{1-r}\right)^2+\left(1-\left(\frac{r}{1-r}\right)^2\right)y^2=1\]);~ //求める楕円体の中心は&imgtex(\[\left(0,\cdots,0,\frac{1}{3}\right)\]);で、~ //体積は、単位超球を&imgtex(\[n-1\]);個の軸の分だけ&imgtex(\[\frac{1-r}//{\sqrt{1-2r}}=\frac{2}{\sqrt{6}}\]);倍、~ //軸1つ分だけ&imgtex(\[1-r=\frac{2}{3}\]);倍したものなので、~ //&imgtex(\[\rho = \frac{2}{3}\left(\frac{2}{\sqrt{6}}\right)^{n-1}\]);~ これより,&imgtex($F$);の射影を&imgtex($\frac{x_1^2}{a^2}+\frac{(x_n-c)^2}{b^2}\le 1$);とすれば,~ &imgtex(\begin{align*}\frac{1}{a^2}+\frac{c^2}{b^2}&=1\\\frac{(1-c)^2}{b^2}&=1\end{align*});~ これを解いて,&imgtex($a^2=\frac{b^2}{2b-1}$);.~ また,&imgtex($\rho=a^{n-1}b$);が最小となるのは&imgtex($a^{2(n-1)}b^2=b^2\left(\frac{b^2}{2b-1}\right)^{n-1}$);が最小となる&imgtex($b$);を求めればよい.~ &imgtex($b$);で微分すると,&imgtex(\[\left(\frac{b^2}{2b-1}\right)^{n-1}\frac{2}{2b-1}((n+1)b-n)\]);より,&imgtex(\[b=\frac{n}{n+1}\]);で最小.~ 以上より,~ &imgtex(\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*});~ 中心の座標は&imgtex(\[\begin{pmatrix}0&0&\dots&0&c\end{pmatrix}=\begin{pmatrix}0&\dots&0&\frac{1}{n+1}\end{pmatrix}\]); --(2)上で求めた&imgtex($\rho$);に関して,&imgtex($n\to\infty$);のとき &imgtex($\log\rho$);が0に収束することを示し, さらに,その収束の速さを論ぜよ. ---&imgtex($\lim_{n\to\infty}\rho$);は,~ &imgtex(\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*});~ となるので,&imgtex($\lim_{n\to\infty}\log\rho\to 0$);.~ &imgtex(\[(n-1)\log\left(1+\frac{1}{n-1}\right)\simeq 1-\frac{1}{2}\frac{1}{n-1}+O(1/n^2)\]);~ &imgtex(\[(n+1)\log\left(1-\frac{1}{n+1}\right)\simeq -1-\frac{1}{2}\frac{1}{n+1}+O(1/n^2)\]);~ これより,~ &imgtex(\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*});~ となるので,収束の速さは&imgtex($O(1/n)$);. --(3)一般の場合の&imgtex($E,H$);に対して, &imgtex($\rho$);が&imgtex($E,H$);に依らず,&imgtex($n$);だけの関数であることを説明せよ. ---適当な1次変換をすることで原点を中心とした楕円体は原点を中心とした球に変換できる.また,1次変換によって体積の比は変わらないので&imgtex($\rho$);は&imgtex($n$);だけの関数になる. ---- -第3問~ --(1)平面上に平行な直線が等間隔に引かれている. 隣り合う2直線の間隔を1とする. この平面状に長さ1の針をランダムに投げる. 針が直線群と交わる確率&imgtex($p$);を求めよ. ---すぐ下の直線から針の重心までの距離が&imgtex($d$);で直線となす角が&imgtex($\theta$);であるとする.すると面積を考えて,~ &imgtex(\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)針を&imgtex($n$);回投げ,針が直線群と交わった回数&imgtex($X$);を記録する実験を行う.&imgtex($X/n$);の分散を求めよ. &imgtex($\sqrt{n}\left(\frac{X}{n}-p\right)$);の従う分布は, &imgtex($n\to\infty$);のときどのような分布に収束するか. ---2項分布なので,&imgtex($X$);の分散は&imgtex($np(1-p)$);. よって,&imgtex($X/n$);の分散は&imgtex($p(1-p)/n$);. また,中心極限定理より&imgtex($\sqrt{n}\left(\frac{X}{n}-p\right)$);の従う分布は平均&imgtex($0$);,分散&imgtex($p(1-p)$);の正規分布になる. --(3)1辺の長さが1の正&imgtex($m$);角形&imgtex($(m\ge 3)$);を平面状にランダムに投げる.正&imgtex($m$);角形の周と直線群との交点の個数&imgtex($Y$);の期待値を求めよ. ---期待値の線型性より,&imgtex($Y=m*\frac{2}{\pi}=\frac{2m}{\pi}$);. ---- -第4問~ 一般に,同じ大きさの正方行列&imgtex($P,Q$);に対して, 記号&imgtex($[P,Q]$);は,行列&imgtex($PQ-QP$);を表すものとする. 同じ大きさの実対称行列&imgtex($U()t)$);に関する微分方程式の初期値問題~ &imgtex(\begin{align*}\frac{d}{dt}U(t)&=[A,U(t)BU(t)^{\top}]U(t),\\U(0)&=I\end{align*});~ を考える.~ --(1)任意の&imgtex($t>0$);に対して&imgtex($U(t)^{\top}U(t)=I$);であることを示せ. ---&imgtex($(U(t)BU(t)^{\top})^{\top}=(U(t)BU(t)^{\top})$);なので,であり, &imgtex($P,Q$);が実対称行列のとき&imgtex($[P,Q]+[P,Q]^{\top}=(PQ-QP)+(Q^{\top}P^{\top}-P^{\top}Q^{\top}=0)$);であることに注意して,~ &imgtex(\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*});~ なので,任意の&imgtex($t>0$);に対して&imgtex($U(t)=U(0)=I$);である. --(2)行列&imgtex($X(t)=U(t)BU(t)^{\top}$);は,任意の&imgtex($t>0$);に対して,~ &imgtex(\begin{align*}\frac{d}{dt}\mathrm{Tr}(AX(t))=\mathrm{Tr}([A,X(t)]A,X(t)]^{\top})\end{align*});~ を満たすことを示せ. ---&imgtex($\mathrm{Tr}(AB)=\mathrm{Tr}(BA)$);なので,~ &imgtex(\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)任意の&imgtex($t>0$);に対して~ &imgtex(\begin{align*}\frac{d}{dt}\mathrm{Tr}(AX(t))\ge 0\end{align*});~ であり,&imgtex($t\to\infty$);の極限において~ &imgtex(\begin{align*}\frac{d}{dt}\mathrm{Tr}(AX(t))\to 0\end{align*});~ となることを示せ. --- --(4)&imgtex($A$);が相異なる実数を対角要素とする対角行列であるとき, &imgtex($t\to\infty$);の極限において&imgtex($X(t)$);が&imgtex($B$);の固有値を対角成分とする対角行列に収束することを示せ. ---&imgtex($\frac{d}{dt}\mathrm{Tr}(AX(t))=\mathrm{Tr}([A,X(t)][A,X(t)]^{\top})\to 0$);であり,~ &imgtex(\begin{align*}\mathrm{Tr}([A,X(t)][A,X(t)]^{\top})&=(a_{ii}-a_{jj})^2x_{ij}^2\to 0.\end{align*});~ ここで,&imgtex($A$);の対角成分は全て異なるので, &imgtex($X(t)$);は対角行列に収束する.~ また&imgtex($U(t)$);は(1)より直交行列なので, &imgtex($X(t)$);の固有値は&imgtex($B$);の固有値に等しい. よって,&imgtex($X(t)$);は&imgtex($B$);の固有値を対角成分とする対角行列に収束する. ---- -第5問~ 円周上に&imgtex($N$);個の点があるとする(&imgtex($N\ge 4$);). その中の一つの点から初めて時計回りに順に &imgtex($P_0,P_1,\dots,P_{N-1}$);とする. 円の中心を原点とする正規直交座標系における各点&imgtex($P_i$);の 座標&imgtex($x_i,y_i$);がいずれも有理数であって,これらが与えられているものとする. 次のそれぞれの問題に大して,&imgtex($N$);に関して線型時間のアルゴリズムを設計せよ. --(1)&imgtex($P_0,P_1,\dots,P_{N-1}$);の中に直径の両端点となる2点が存在するかどうかを判定する問題. ---&imgtex($i=0,j=1,V=[]$);,flag=FALSEと初期化する.~ &imgtex($i==j$);または&imgtex($j\ge N$);ならば終了しflagを返す.~ 角&imgtex($P_iO$);と&imgtex($P_iP_j$);の外積が正のときは&imgtex($j$); をインクリメント,負のときは&imgtex($i$);をインクリメントし,0のときは flag=TRUEとし,&imgtex($V$);を&imgtex($V=(P_i,P_j):V$);に更新する.~ 毎回&imgtex($i,j$);のどちらかはインクリメントされるので時間計算量は&imgtex($O(N)$);. --(2)&imgtex($P_0,P_1,\dots,P_{N-1}$);の中の4点を頂点とする長方形が存在するかどうかを判定する問題. --- (1)のアルゴリズムを用いれば,円の直径の両端点となる2点の集合が分かるので, その集合の大きさが2以上であれば存在する.線型時間. --(3)&imgtex($P_0,P_1,\dots,P_{N-1}$);の中の4点を頂点とする長方形の中で面積が最大となるものを求める問題. ---(1)のアルゴリズムを走らせて,円の直径の両端点となる2点の集合&imgtex($V=[V_0=(F_0,T_0),\dots,V_{n-1}=(F_{n-1},T_{n-1})]$);をもとめる. &imgtex($i=0,j=0,\mathrm{max}=0$);と初期化する. &imgtex($F_iOF_j\le \pi/4< F_iOF_{(j+1)\%n}$);となるまで&imgtex($j$);をインクリメントして,&imgtex($\mathrm{max}$);を現在の値と&imgtex($V_i,V_j$);を使ったときの長方形の面積の値と&imgtex($V_{i},V_{(j+1)\%n}$);を使ったときのそれの最大値に更新する.&imgtex($i<n$);なら&imgtex($i$);をインクリメントする.~ というアルゴリズムを用いればよい. ---- コメント - お客様の中で第2問が解けた方はいらっしゃいませんか. -- [[yambi]] &new{2008-08-14 (木) 12:25:12}; - 第2問どころか、第1問も第5問も解けませんでした。泣いていいですか? -- [[muk]] &new{2008-08-14 (木) 23:33:12}; - 第2問で、ρがああなるのはなぜなんでしょうか?だれか御教授くださいm(_ _)m -- [[muk]] &new{2008-08-18 (月) 10:07:07}; - &imgtex($\rho$);は単位球と楕円体の体積比なので,各軸方向について長さの比の積となります. -- [[yambi]] &new{2008-08-18 (月) 13:38:41}; - 1-(2)のグリーディーってのがよくわからない…∑pjaj1<p1∑aj1は分かるんだけど…添え字が増えたときにどう処理するんだろう -- [[tako]] &new{2008-08-24 (日) 17:15:12}; - 各jについて&imgtex($\sum_{i=1}^k a_{ij}\le 1$);で,&imgtex($\sum_{i,j}a_{ij}=k$);なので,大きいほうからとればいいという適当な変形です. -- [[yambi]] &new{2008-08-24 (日) 17:34:27}; - 4-(2),(3)あたりですが、[A,X]って、転置すると負になるということは、対角成分は0?で、上三角とその転置の下三角の差としてあらわしていいですか?すると(3)おかしくなる気がする… -- [[tako]] &new{2008-08-24 (日) 19:09:33}; - あ、なるほど、各pについて、1に足りない分借りてくるみたいなイメージで貪欲なのか…なんとなくわかりました。 -- [[tako]] &new{2008-08-24 (日) 19:15:53}; - [A,X]=Cと表すことにする.cij=-cjiであり、CC^Tの対角成分(k,k)は、&imgtex($ \sum a_{k,j}a_{} $); -- [[tako]] &new{2008-08-24 (日) 19:25:57}; - [A,X]=Cと表すことにする。&imgtex($ C^T=-C \Rightarrow c_{i,j}=-c_{j,i} $);であり、CC^Tの対角成分(k,k)は、&imgtex($ \sum c_{k,i}(-c_{k,i}) \le 0 $); -- [[tako]] &new{2008-08-24 (日) 19:25:57}; #comment