東大 情報理工学系研究科 数理情報学専攻 数理情報学 2026年度 院試 解答例・解説

方針

この問題の核は、半正定値錐へのユークリッド射影である。フロベニウスノルムと半正定値性は直交変換で保たれるので、対称行列を固有値分解してスカラーの問題に落とすのが最短である。

一意性を落とさない

固有値が重複すると固有ベクトルの選び方は一意でないが、正固有空間への射影として見れば $\phi(A)$ は一意である。この点を書いておくと、答案として安定する。

相補性の見方

最後の同値性は、凸錐の射影と相補性条件を結ぶ典型形である。特に $\operatorname{tr}(XY)=0$ からすぐ $XY=0$ と書くのではなく、 $X^{1/2}YX^{1/2}\succeq0$ のトレースが $0$ だから零行列になる、という一段を入れると減点されにくい。

使う道具

本問は、正規分布のモーメント母関数、Markov の不等式、union bound の三つで完結する。ランダム行列の問題に見えるが、固定した $b$ に対しては各行との内積が標準正規になるだけである。

定数の出し方

指数の定数 $8$ は、$\lambda=\varepsilon/(4m)$ と置いて、与えられた対数不等式を $\log(1-2\lambda)$ に使うことで出る。最適な $\lambda$ を解いてもよいが、試験ではこの選択の方が速く、指定された定数に合わせやすい。

全組への拡張

最後は Johnson--Lindenstrauss 型の議論である。ただし両側評価ではなく上側だけなので、必要なのは上側集中と有限個の組に対する union bound だけである。

不変領域は境界を見る

$x=0$、$y=0$、$x+y=1$ の三つの境界に対して、ベクトル場が外側へ出ないことを確認するのが基本方針である。ここでは指数表示を使うと $x,y$ の正性まで直接示せる。

保存量の使いどころ

$\frac{dy}{dx}$ を使うと一次の微分方程式になり、保存量が出る。極限値の議論では保存量だけでなく、$x(t)$ が単調で極限を持つことも先に書く必要がある。

発散の判定

有限時刻爆発は、$\dot x$ が少なくとも $x^2$ 程度で増えることを示せば十分である。$\int^\infty u^{-2}\,du$ が有限であるため、無限大に到達するまでの時間も有限になる。

出生死滅連鎖として見る

この過程では一回に $X_t$ は $+1$、$-1$、または変化なしにしかならない。従って本質は一次元の出生死滅連鎖であり、吸収確率も期待吸収時刻も第一ステップ解析で差分方程式に落ちる。

比 $p_i/q_i$ が一定になる利点

一般の出生死滅連鎖では $\prod q_i/p_i$ が出るが、この問題では比が常に $1/r$ なので等比数列だけで解ける。$r=1$ は極限としても得られるが、答案では別に書く方が明確である。

期待時刻の符号確認

期待時刻の式では右辺が $-1$ になる。これは「一歩進めると時間を1消費する」ためであり、符号を逆にすると $T_i$ が負になるので検算しやすい。

差分グラフを見る

一意性の証明では、二つの向き付けの違う辺だけを見るのが要点である。入次数が同じなら、その差分部分では各頂点の入次数と出次数が釣り合う。非空なら有向閉路を含むので、非巡回性と矛盾する。

削除法はトポロジカルソートの一般化

指定入次数列の判定アルゴリズムは、通常のトポロジカルソートに「残り入次数を指定値から引いていく」処理を加えたものと見ればよい。負になった時点で、すでに必要以上の入辺を使ってしまったことを意味する。

最適化の二つの型

最大入次数の最小化は大域的な順序の問題で、degeneracy が答になる。一方、線形重みの最大化は各辺の寄与が独立なので、局所的に大きい重みへ向ければよい。ただし非巡回性を保つため、同じ重みの中では添字で向きを統一する。