座標平面において,$x$ 座標も $y$ 座標も整数である点全体の集合上を移動する点 $\mathrm{P}$ がある。時刻 $0$ に点 $\mathrm{P}$ は原点 $\mathrm{O}$ にある。$0$ 以上の整数 $t$ に対し,時刻 $t$ に点 $\mathrm{P}$ が点 $(m,n)$ にあるとき,時刻 $t+1$ での点 $\mathrm{P}$ の位置は $4$ 点
$$
(m+1,n),\quad (m-1,n),\quad (m,n+1),\quad (m,n-1)
$$
のいずれかであり,また,どの位置にある確率も $\dfrac{1}{4}$ である。以下の問いに答えよ。
(1) 時刻 $8$ に点 $\mathrm{P}$ が点 $(4,0)$ にある確率を求めよ。
(2) 時刻 $8$ に点 $\mathrm{P}$ が双曲線 $x^2-y^2=16$ 上にある確率を求めよ。
(3) 時刻 $8$ に点 $\mathrm{P}$ が双曲線 $x^2-y^2=16$ 上にあるとき,時刻 $1$,時刻 $2$,$\cdots$,時刻 $7$ のいずれかに点 $\mathrm{P}$ が点 $(4,2)$ にある条件付き確率を求めよ。
$t\geqq0$,$z=(x,y)\in\mathbb{Z}^2$ とする。
(i) $N_t(z) > 0$ であるための必要十分条件は,$\lVert z\rVert_1\leqq t$ かつ $x+y\equiv t\pmod 2$ である。
(ii) $\lVert z\rVert_1=t$ のとき,$z$ に至る移動列は,水平方向には $x$ の符号の向きにだけ $|x|$ 回,鉛直方向には $y$ の符号の向きにだけ $|y|$ 回進むものに限られる。特に $N_t(z)=\binom{t}{|x|}$ である。
(i) 一歩で $|x|$,$|y|$ の一方だけがちょうど $1$ 変化するから,$\lVert\mathrm{P}_k\rVert_1$ は一歩ごとに $\pm1$ 変化する。また $X_k+Y_k$ も一歩ごとに $\pm1$ 変化する。よって $\lVert\mathrm{P}_t\rVert_1\leqq t$ と $X_t+Y_t\equiv t\pmod2$ が必要である。逆に条件をみたすとき,$\lVert z\rVert_1$ 歩の最短の移動列の後に $\mathsf{E}\mathsf{W}$ を $(t-\lVert z\rVert_1)/2$ 組(偶奇の条件から整数)続ければ $z$ に至る。
(ii) 東・西・北・南への移動回数を $e,w,n,s$ とすると $x=e-w$,$y=n-s$ であり,
$$
t=e+w+n+s\geqq|e-w|+|n-s|=\lVert z\rVert_1 .
$$
等号は $\min(e,w)=\min(n,s)=0$ のときに限る。よって $\lVert z\rVert_1=t$ なら逆向きの移動は現れず,$(e,w,n,s)$ は $z$ から一意に定まる。並べ方は $\binom{t}{|x|}$ 通りである。
時刻 $8$ に到達可能な点は,菱形 $\lVert z\rVert_1\leqq8$ に含まれ $x+y$ が偶数の格子点である。境界 $\lVert z\rVert_1=8$ の上では遠回りが一歩も許されず,経路数は二項係数一つで与えられる。
$$
H=\lbrace(4,0),\ (-4,0),\ (5,3),\ (5,-3),\ (-5,3),\ (-5,-3)\rbrace .
$$
これらはすべて時刻 $8$ に到達可能であり,$\lVert(\pm4,0)\rVert_1=4$,$\lVert(\pm5,\pm3)\rVert_1=8$ である。
$u=x+y$,$v=x-y$ とおくと $x^2-y^2=uv$ であり,$u-v=2y$ より $u\equiv v\pmod2$ である。$uv=16$ は偶数だから $u,v$ はともに偶数であり,$u=2u'$,$v=2v'$ とおくと $u'v'=4$ となる。よって
$$
(u,v)\in\lbrace(2,8),\ (4,4),\ (8,2),\ (-2,-8),\ (-4,-4),\ (-8,-2)\rbrace .
$$
逆にこれらは $x=\frac{u+v}{2}$,$y=\frac{u-v}{2}$ により,順に整数点 $(5,-3),(4,0),(5,3),(-5,3),(-4,0),(-5,-3)$ を与える。各点で $x+y=u$ は偶数,$\lVert\cdot\rVert_1\leqq8$ であるから,
補題1
により時刻 $8$ に到達可能である。
$H$ の6点は,座標の符号反転で移り合う二つの型に分かれる。
| 型 | 点 | 個数 | $\lVert z\rVert_1$ | 時刻 $8$ での経路 |
|---|---|---|---|---|
| I | $(\pm4,0)$ | $2$ | $4$ | 往復 $2$ 組分の余裕がある |
| II | $(\pm5,\pm3)$ | $4$ | $8$ | 全 $8$ 歩が最短経路 |
歩行は $x$ と $y$ の交換についても対称であるが,交換は $H$ を双曲線 $y^2-x^2=16$ に移すので,$(\pm3,\pm5)$ は $H$ に属さない。$H$ に対して使える対称性は符号反転だけである( 1.5 節 )。
$1\leqq t\leqq7$ のうち $\lbrace\mathrm{P}_t=(4,2)\rbrace\neq\varnothing$ となるのは $t=6$ のみである。したがって
$$
A=\lbrace\mathrm{P}_6=(4,2)\rbrace .
$$
さらに時刻 $6$ までの移動は $\mathsf{E}$ 4回と $\mathsf{N}$ 2回の並べ替えに限られ,$N_6(4,2)=\binom{6}{2}=15$ である。
「時刻 $1$ から $7$ のいずれか」という7個の事象の和は,実質的に一つの事象である。同じ移動列が複数の時刻に $(4,2)$ を訪れることもないから,包除原理や初到達時刻による分解は必要ない。
$\lbrace\mathsf{E},\mathsf{W},\mathsf{N},\mathsf{S}\rbrace$ を保つ $\mathbb{Z}^2$ の線形変換の全体を $G$ とする。$G$ は $(x,y)\mapsto(\pm x,\pm y),\ (\pm y,\pm x)$ の8個からなる位数 $8$ の二面体群である。$g\in G$ に対し $\sigma\mapsto(g\sigma_1,\ldots,g\sigma_t)$ は $\Omega_t$ の全単射で,終点を $g$ で移す。よって
$$
N_t(gz)=N_t(z)\qquad(g\in G).
$$
$H$ を保つのは $G$ のうち符号反転 $(x,y)\mapsto(\pm x,\pm y)$ の4個であり(
1.3 節
),
$$
N_8(H)=2N_8(4,0)+4N_8(5,3).
$$
$0\leqq s\leqq t$,$z\in\mathbb{Z}^2$,$K\subset\mathbb{Z}^2$ に対し,$K-z=\lbrace w-z:\ w\in K\rbrace$ とおくと
$$
\bigl|\lbrace\sigma\in\Omega_t:\ \mathrm{P}_s=z,\ \mathrm{P}_t\in K\rbrace\bigr|=N_s(z)\,N_{t-s}(K-z).
$$
$\sigma\mapsto\bigl((\sigma_1,\ldots,\sigma_s),(\sigma_{s+1},\ldots,\sigma_t)\bigr)$ は $\Omega_t$ から $\Omega_s\times\Omega_{t-s}$ への全単射であり,$\mathrm{P}_t=\mathrm{P}_s+(\sigma_{s+1}+\cdots+\sigma_t)$ である。左辺の集合は,前半が $z$ に至り後半の変位が $K-z$ に属する組の全体と一対一に対応する。
補題3
と合わせると
$$
|A\cap B|=N_6(4,2)\,N_2\bigl(H-(4,2)\bigr)
$$
である。これは Markov 性の組合せ論的な表現であり,(3) のすべての解法に共通する骨格である。
$U_t=X_t+Y_t$,$V_t=X_t-Y_t$ とおくと,一歩の変化は次のとおりである。
| 一歩 | $\mathsf{E}$ | $\mathsf{W}$ | $\mathsf{N}$ | $\mathsf{S}$ |
|---|---|---|---|---|
| $(\Delta X,\Delta Y)$ | $(1,0)$ | $(-1,0)$ | $(0,1)$ | $(0,-1)$ |
| $(\Delta U,\Delta V)$ | $(1,1)$ | $(-1,-1)$ | $(1,-1)$ | $(-1,1)$ |
4方向と符号の組 $\lbrace1,-1\rbrace^2$ が一対一に対応する。さらに
$$
X_t^2-Y_t^2=U_tV_t,\qquad \lVert(x,y)\rVert_1=\max\bigl(|x+y|,\ |x-y|\bigr)
$$
であるから,双曲線 $x^2-y^2=16$ は $uv=16$ に,到達可能な菱形 $\lVert z\rVert_1\leqq t$ は正方形 $|u|\leqq t,\ |v|\leqq t$ に変わる。終点条件と移動規則が,同じ一次形式 $x\pm y$ によって同時に分解される。
任意の $t\geqq0$,$(x,y)\in\mathbb{Z}^2$ に対し
$$
N_t(x,y)=c_t(x+y)\,c_t(x-y).
$$
また $\Omega_t$ 上の一様分布のもとで $U_t$ と $V_t$ は独立であり,$\Pr(U_t=u)=\Pr(V_t=u)=c_t(u)/2^t$ である。
上の表の対応 $\phi:\lbrace\mathsf{E},\mathsf{W},\mathsf{N},\mathsf{S}\rbrace\to\lbrace1,-1\rbrace^2$,$\phi(d)=(\Delta U,\Delta V)$ は全単射である。よって $\sigma\mapsto(\varepsilon,\eta)$,$(\varepsilon_i,\eta_i)=\phi(\sigma_i)$ は $\Omega_t$ から $\lbrace\pm1\rbrace^t\times\lbrace\pm1\rbrace^t$ への全単射であり,$U_t=\sum_i\varepsilon_i$,$V_t=\sum_i\eta_i$ である。$(x+y,\ x-y)$ は $(x,y)$ を一意に定めるから,$\mathrm{P}_t=(x,y)$ は「$\sum_i\varepsilon_i=x+y$ かつ $\sum_i\eta_i=x-y$」と同値であり,このような $(\varepsilon,\eta)$ の個数は $c_t(x+y)\,c_t(x-y)$ である。一様分布はこの全単射によって $\lbrace\pm1\rbrace^t\times\lbrace\pm1\rbrace^t$ 上の一様分布に移るから,$\varepsilon$ と $\eta$ は独立である。
元の座標 $X_t,Y_t$ は独立ではない。たとえば $\Pr(X_1=0)=\Pr(Y_1=0)=\frac12$ であるが $\Pr(X_1=Y_1=0)=0$ である。独立になるのは斜め座標 $U_t,V_t$ であり,その根拠は「4方向が4つの符号の組に一対一に対応し,しかも等確率である」ことにある( 5.3 節 )。
以上の構造から,作問の設計は次のように読める(数値設定からの分析であり,出題者の意図についての推定を含む)。
| 着目する構造 | 数学的翻訳 | 導かれる解法 |
|---|---|---|
| 方向別の回数と終点の一次条件 | 多項係数の和,境界での最短経路 | 本解 |
| 一歩の4方向と符号の組の対応 | 斜め座標,二項係数の積 | 別解1,3.2 節 |
| 動く軸の選択と向きの選択の分離 | 水平移動の回数による条件付け | 参考解1 |
| 最後の一歩による分類 | 隣接4点からの漸化式 | 参考解2 |
| 絶対値の平方差 | $(\lvert x\rvert+\lvert y\rvert)(\lvert x\rvert-\lvert y\rvert)=16$ | 3.1 節 |
| 通過時刻の一意性と経路の連結 | 終点による分解,Bayes の公式 | 3.3 節 |
東・西・北・南への移動回数を未知数とし,終点の条件を一次方程式にして多項係数で数える。(2) では $H$ の6点( 補題2 )を符号反転の対称性で2型に整理し,型 II は境界上の最短経路として数える。(3) では距離と偶奇によって通過時刻を $6$ に固定し( 補題3 ),前半6歩と後半2歩の経路数の積をとる( 補題4 )。
東・西・北・南への移動回数を非負整数 $e,w,n,s$ とする。$\mathrm{P}_8=(4,0)$ となる条件は
$$
e-w=4,\qquad n-s=0,\qquad e+w+n+s=8
$$
である。$w=k$ とおくと $e=4+k$,$n=s=2-k$ であり,$n\geqq0$ より $k\in\lbrace0,1,2\rbrace$ である。回数の組を固定したときの移動列の数は多項係数で与えられるから
$$
\begin{aligned}
N_8(4,0)&=\sum_{k=0}^{2}\frac{8!}{(4+k)!\,k!\,\bigl((2-k)!\bigr)^2}
=\frac{8!}{4!\,2!\,2!}+\frac{8!}{5!\,1!\,1!\,1!}+\frac{8!}{6!\,2!}\\
&=420+336+28=784 .
\end{aligned}
$$
したがって
$$
\Pr\bigl(\mathrm{P}_8=(4,0)\bigr)=\frac{784}{4^8}=\frac{49}{4096}.
$$
$x^2-y^2=(x+y)(x-y)=16$ において,$x+y$ と $x-y$ は差が $2y$ であるから偶奇が一致し,積が偶数であるからともに偶数である。$\frac{x+y}{2}\cdot\frac{x-y}{2}=4$ より
$$
H=\lbrace(\pm4,0),\ (\pm5,\pm3)\rbrace\qquad(\text{複号任意,6点})
$$
である(
補題2
)。符号反転 $(x,y)\mapsto(\pm x,\pm y)$ は東西・南北の入れ替えによって移動列の全単射を与えるから,$N_8(-4,0)=N_8(4,0)=784$,$N_8(\pm5,\pm3)=N_8(5,3)$ である。
$(5,3)$ については,$e-w=5$,$n-s=3$ の和と $e+w+n+s=8$ を比べて $2(w+s)=0$,すなわち $w=s=0$,$e=5$,$n=3$ を得る。よって
$$
N_8(5,3)=\binom{8}{3}=56 .
$$
ゆえに
$$
N_8(H)=2\cdot784+4\cdot56=1792,\qquad \Pr(B)=\frac{1792}{4^8}=\frac{7}{256}.
$$
一歩で $|x|+|y|$ は $1$ だけ増減し,$x+y$ の偶奇は毎回入れ替わる。$(4,2)$ では $|x|+|y|=6$,$x+y=6$ であるから,$(4,2)$ にいる時刻は $6$ 以上の偶数である。よって時刻 $1$ から $7$ のうちで可能なのは時刻 $6$ だけであり,$A=\lbrace\mathrm{P}_6=(4,2)\rbrace$ である。時刻 $6$ までの移動は $\mathsf{E}$ 4回と $\mathsf{N}$ 2回に限られ,その並べ方は
$$
N_6(4,2)=\binom{6}{2}=15
$$
通りである。
次に,時刻 $6$ に $(4,2)$ にいて,残り2歩で $H$ に至る移動を数える。2歩で到達できるのは $(4,2)$ からの $\ell^1$ 距離が $2$ 以下の点であり,$H$ の各点との距離は
$$
(4,0):\ 2,\qquad (5,3):\ 2,\qquad (5,-3):\ 6,\qquad (-4,0):\ 10,\qquad (-5,3):\ 10,\qquad (-5,-3):\ 14
$$
である。距離がちょうど $2$ の点へは最短経路に限られるから,最後の2歩は
$$
(4,0)\ \text{へ}:\ \mathsf{S}\mathsf{S}\ \ (1\ \text{通り}),\qquad (5,3)\ \text{へ}:\ \mathsf{E}\mathsf{N},\ \mathsf{N}\mathsf{E}\ \ (2\ \text{通り})
$$
の3通りである。前半6歩と後半2歩は独立に選べるから(
補題4
)
$$
|A\cap B|=15\times3=45 .
$$
したがって
$$
\Pr(A\mid B)=\frac{\Pr(A\cap B)}{\Pr(B)}=\frac{45/4^8}{1792/4^8}=\frac{45}{1792}.
$$
| 設問 | 経路数 | 確率 |
|---|---|---|
| (1) | $N_8(4,0)=784$ | $\dfrac{49}{4096}$ |
| (2) | $N_8(H)=1792$ | $\dfrac{7}{256}$ |
| (3) | $\lvert A\cap B\rvert=45$ | $\dfrac{45}{1792}$ |
3.1〜3.3 節は本解の一部を置き換える別証・他の導出,3.4 節は経路の表現を取り替える別解,3.5〜3.6 節は計算の原理を変える参考解である。
$x^2-y^2=|x|^2-|y|^2=(|x|+|y|)(|x|-|y|)$ の第1因子は $\lVert z\rVert_1$ そのものである。因数分解と到達可能性が同じ量で結び付き,点の決定と経路の型の判定を同時に行える。
$z=(x,y)\in H$ とし,$r=|x|+|y|$,$q=|x|-|y|$ とおく。$rq=16$ と $r\geqq0$ より $r > 0$,$q > 0$ であり,$q\leqq r$ である。$r-q=2|y|$ より $r\equiv q\pmod2$ であり,$rq$ は偶数であるから $r,q$ はともに偶数である。$rq=16$,$0 < q\leqq r$ をみたす偶数の組は $(r,q)=(4,4),\ (8,2)$ のみであるから
$$
(|x|,|y|)=\Bigl(\frac{r+q}{2},\ \frac{r-q}{2}\Bigr)=(4,0),\ (5,3).
$$
よって $H=\lbrace(\pm4,0),(\pm5,\pm3)\rbrace$ である。さらに $\lVert z\rVert_1=r\in\lbrace4,8\rbrace$,$x+y\equiv r\equiv0\pmod2$ であるから,
補題1
によりいずれも時刻 $8$ に到達可能である。
$r$ の値がそのまま型を与える。$r=4$ は余裕 $8-4=4$(往復2組),$r=8$ は余裕 $0$(最短経路)であり, 1.3 節 の表と一致する。$(r,q)=(16,1)$ は偶奇の条件で除かれるから,到達可能性 $r\leqq8$ を用いなくても $H$ 全体が決まる。
一歩を単項式 $z^{\pm1}$,$w^{\pm1}$ で表すと,$t$ 歩の経路数は Laurent 多項式の $t$ 乗の係数になる。一歩の多項式が二つの一変数多項式の積に分解されれば, 補題5 は係数の積として従う。
$F(z,w)=z+z^{-1}+w+w^{-1}$ とおく。$F^t$ を展開すると,$t$ 個の因子のそれぞれから一歩を選ぶ選び方が移動列に対応するから
$$
F(z,w)^t=\sum_{(x,y)\in\mathbb{Z}^2}N_t(x,y)\,z^xw^y .
$$
$z=ab$,$w=ab^{-1}$ を代入すると $z^xw^y=a^{x+y}b^{x-y}$ であり,$(x,y)\mapsto(x+y,\ x-y)$ は単射であるから,相異なる単項式は相異なる単項式に移り,係数は保たれる。一方
$$
F(ab,ab^{-1})=ab+a^{-1}b^{-1}+ab^{-1}+a^{-1}b=(a+a^{-1})(b+b^{-1})
$$
であり,$(a+a^{-1})^t=\sum_u c_t(u)\,a^u$ であるから
$$
\sum_{(x,y)\in\mathbb{Z}^2}N_t(x,y)\,a^{x+y}b^{x-y}=\Bigl(\sum_{u}c_t(u)\,a^u\Bigr)\Bigl(\sum_{v}c_t(v)\,b^v\Bigr).
$$
両辺の $a^{x+y}b^{x-y}$ の係数を比べて $N_t(x,y)=c_t(x+y)\,c_t(x-y)$ を得る。右辺で $c_t(u)c_t(v)\neq0$ となるのは $u\equiv v\equiv t\pmod 2$ のときに限るから,右辺の単項式はすべて左辺の形 $a^{x+y}b^{x-y}$ をもつ。
$t=1$ では $(a+a^{-1})(b+b^{-1})$ の4項が4方向に対応する。$t=2$,$(x,y)=(0,0)$ では $c_2(0)^2=4$ となり,移動列 $\mathsf{E}\mathsf{W},\mathsf{W}\mathsf{E},\mathsf{N}\mathsf{S},\mathsf{S}\mathsf{N}$ の数と一致する。
$B$ は6個の終点に分かれる。終点を固定すれば,経由の条件付き確率は「前半の経路数 × 後半の経路数 ÷ 全体の経路数」となり,これを $B$ のもとでの終点の分布で平均すればよい。あるいは $\Pr(A)$,$\Pr(B\mid A)$ を先に求めて Bayes の公式を用いる。
$0\leqq s\leqq T$,$z,w\in\mathbb{Z}^2$,$N_T(w) > 0$ とする。$\Omega_T$ 上の一様分布のもとで
$$
\Pr(\mathrm{P}_s=z\mid \mathrm{P}_T=w)=\frac{N_s(z)\,N_{T-s}(w-z)}{N_T(w)} .
$$
補題4 で $t=T$,$K=\lbrace w\rbrace$ とした式の両辺を $N_T(w)$ で割ればよい。
補題3
より $A=\lbrace\mathrm{P}_6=(4,2)\rbrace$ である。$w\in H$ に対し $w-(4,2)$ は
$$
(0,-2),\quad (1,1),\quad (1,-5),\quad (-8,-2),\quad (-9,1),\quad (-9,-5)
$$
であり,$N_2$ が正となるのは最初の2つで,$N_2(0,-2)=1$,$N_2(1,1)=2$ である。よって
$$
\Pr\bigl(A\mid\mathrm{P}_8=(4,0)\bigr)=\frac{15\cdot1}{784}=\frac{15}{784},\qquad \Pr\bigl(A\mid\mathrm{P}_8=(5,3)\bigr)=\frac{15\cdot2}{56}=\frac{15}{28}
$$
であり,$H$ の他の4点では $0$ である。$\Pr(\mathrm{P}_8=w\mid B)=N_8(w)/1792$ で重み付けると,全確率の公式より
$$
\Pr(A\mid B)=\frac{784}{1792}\cdot\frac{15}{784}+\frac{56}{1792}\cdot\frac{15}{28}=\frac{15}{1792}+\frac{30}{1792}=\frac{45}{1792}.
$$
Bayes の公式による場合,
補題4
より $|A|=15\cdot4^2$,$|A\cap B|=15\cdot3$ であるから $\Pr(A)=\frac{15}{4^6}$,$\Pr(B\mid A)=\frac{3}{16}$ であり
$$
\Pr(A\mid B)=\frac{\Pr(A)\,\Pr(B\mid A)}{\Pr(B)}=\frac{\frac{15}{4096}\cdot\frac{3}{16}}{\frac{7}{256}}=\frac{45}{1792}.
$$
条件 $B$ のもとで終点が型 I にある確率は $\frac{2\cdot784}{1792}=\frac78$ であるが,分子 $45$ への寄与は型 I が $15$,型 II が $30$ である。型 II の終点 $(5,3)$ への経路は単調な格子路 $\binom{8}{3}=56$ 本であり,そのうち $(4,2)$ を通るものは $\binom{6}{2}\binom{2}{1}=30$ 本である(超幾何分布, 5.4 節 )。寄与の比 $15:30$ は,本解の後半2歩の内訳 $1:2$ に一致する。
双曲線の因数 $x+y$,$x-y$ を新しい座標にとると,一歩は二つの独立な $\pm1$ の選択になる( 1.6 節 )。経路数は二項係数の積 $c_t(x+y)\,c_t(x-y)$ となり,(2) は $U_8V_8=16$ をみたす偶数の組の列挙に帰着する。$H$ の決定と経路数の計算が一度に済む。
$U_t=X_t+Y_t$,$V_t=X_t-Y_t$ とする。一歩ごとの $(\Delta U,\Delta V)$ は $(1,1),(-1,-1),(1,-1),(-1,1)$ のいずれかで,4方向と一対一に対応する。
補題5
より,$t$ 歩で $(x,y)$ に至る移動列の数は
$$
N_t(x,y)=c_t(x+y)\,c_t(x-y)
$$
である。時刻 $8$ の一次元の経路数 $c_8(u)$ は次のとおりである($u$ が奇数のときは $0$)。
| $u$ | $\pm8$ | $\pm6$ | $\pm4$ | $\pm2$ | $0$ |
|---|---|---|---|---|---|
| $c_8(u)$ | $1$ | $8$ | $28$ | $56$ | $70$ |
$(x,y)=(4,0)$ は $(u,v)=(4,4)$ に対応するから
$$
N_8(4,0)=c_8(4)^2=\binom{8}{6}^2=784,\qquad \Pr\bigl(\mathrm{P}_8=(4,0)\bigr)=\frac{784}{4^8}=\frac{49}{4096}.
$$
$B=\lbrace U_8V_8=16\rbrace$ である。$U_8,V_8$ は偶数で絶対値は $8$ 以下であるから,$uv=16$ をみたす組は
$$
(u,v)=(2,8),\ (4,4),\ (8,2),\ (-2,-8),\ (-4,-4),\ (-8,-2)
$$
に限られる。$c_8(-u)=c_8(u)$ より
$$
N_8(H)=2\bigl(c_8(2)c_8(8)+c_8(4)^2+c_8(8)c_8(2)\bigr)=2(56+784+56)=1792,\qquad \Pr(B)=\frac{7}{256}.
$$
補題3
より $A=\lbrace\mathrm{P}_6=(4,2)\rbrace=\lbrace(U_6,V_6)=(6,2)\rbrace$ であり
$$
N_6(4,2)=c_6(6)\,c_6(2)=1\cdot15=15 .
$$
残り2歩での $U,V$ の増分を $\alpha,\beta\in\lbrace-2,0,2\rbrace$ とすると,その2歩の移動列の数は $c_2(\alpha)\,c_2(\beta)$ であり,$c_2(\pm2)=1$,$c_2(0)=2$ である。$(U_8,V_8)$ の値ごとの2歩の移動列の数は次の表のとおりである。
| 2歩の移動列の数 | $V_8=0$ | $V_8=2$ | $V_8=4$ |
|---|---|---|---|
| $U_8=4$ | $1$ | $2$ | $1$ |
| $U_8=6$ | $2$ | $4$ | $2$ |
| $U_8=8$ | $1$ | $2$ | $1$ |
$U_8V_8=16$ をみたすのは $(4,4)$ と $(8,2)$ のみであり($U_8=6$ では $V_8=\frac83$ となり不適),その和は $1+2=3$ である。
補題4
より
$$
|A\cap B|=15\cdot3=45,\qquad \Pr(A\mid B)=\frac{45}{1792}.
$$
8歩のうち水平に動く時刻を先に選ぶと,残る自由度は「東西の向き」と「南北の向き」という二つの一次元の符号選択に分かれる。空間の座標ではなく時間を分割して,二つの一次元歩行に帰着させる方法である。
$$ N_t(x,y)=\sum_{k=0}^{t}\binom{t}{k}\,c_k(x)\,c_{t-k}(y). $$
移動列 $\sigma\in\Omega_t$ に,水平に動く時刻の集合 $J\subset\lbrace1,\ldots,t\rbrace$,$J$ 上の東西の符号列,$J$ の補集合上の南北の符号列の三つ組を対応させると全単射である。$|J|=k$ のとき終点が $(x,y)$ となるのは,東西の符号の和が $x$,南北の符号の和が $y$ のときであり,その個数は $\binom{t}{k}c_k(x)\,c_{t-k}(y)$ である。
確率の言葉では,水平移動の回数 $K_t$ は二項分布 $\mathrm{Bin}(t,\frac12)$ に従い,$K_t=k$ のもとで水平・鉛直の成分は長さ $k$,$t-k$ の独立な一次元歩行である。
$c_k(4)\neq0$ には $k\geqq4$ かつ $k$ が偶数,$c_{8-k}(0)\neq0$ には $8-k$ が偶数であることが必要であるから $k\in\lbrace4,6,8\rbrace$ であり
$$
\begin{aligned}
N_8(4,0)&=\binom84c_4(4)\,c_4(0)+\binom86c_6(4)\,c_2(0)+\binom88c_8(4)\,c_0(0)\\
&=70\cdot1\cdot6+28\cdot6\cdot2+1\cdot28\cdot1=420+336+28=784 .
\end{aligned}
$$
$c_k(5)\neq0$ には $k\geqq5$,$c_{8-k}(3)\neq0$ には $8-k\geqq3$ が必要であるから $k=5$ のみであり,$N_8(5,3)=\binom85c_5(5)\,c_3(3)=56$ である。対称性より $N_8(H)=2\cdot784+4\cdot56=1792$。
$N_6(4,2)=\binom64c_4(4)\,c_2(2)=15$ である。後半2歩については $N_2(0,-2)=\binom20c_0(0)\,c_2(-2)=1$,$N_2(1,1)=\binom21c_1(1)\,c_1(1)=2$ であり,$H-(4,2)$ の他の点では $0$ である。よって $|A\cap B|=15\cdot3=45$,$\Pr(A\mid B)=\frac{45}{1792}$。
$k=e+w$ とすると $\binom{t}{k}\binom{k}{e}\binom{t-k}{n}=\dfrac{t!}{e!\,w!\,n!\,s!}$ であるから, 補題7 の各項は本解の多項係数の各項に一致する。実際 $k=4,6,8$ の項 $420,336,28$ は,本解の $w=0,1,2$ の項に順に対応する。参考解1は本解と同じ経路の集合を「軸の選択 → 向きの選択」の順に分類し直したものであり,計算の原理は本解に近い。
時刻 $t+1$ に点 $z$ にいる経路は,時刻 $t$ に $z$ の隣接4点のいずれかにいる。この局所的な規則を時刻 $0$ から積み上げる。(3) では終点側から逆向きに数える関数を併用し,時刻 $6$ で接続する。
$f_t(z)=N_t(z)$ とおく。最後の一歩で分類すると($\Omega_{t+1}=\Omega_t\times\lbrace\mathsf{E},\mathsf{W},\mathsf{N},\mathsf{S}\rbrace$)
$$
f_0(z)=\begin{cases}1 & (z=\mathrm{O})\\ 0 & (z\neq\mathrm{O})\end{cases},\qquad
f_{t+1}(x,y)=f_t(x-1,y)+f_t(x+1,y)+f_t(x,y-1)+f_t(x,y+1).
$$
$G$ による不変性(
1.5 節
)から,$0\leqq y\leqq x$ の代表点だけを保持すればよい。$\rho(a,b)=\bigl(\max(|a|,|b|),\ \min(|a|,|b|)\bigr)$ として漸化式を $f_{t+1}(z)=\sum_{d}f_t\bigl(\rho(z+d)\bigr)$ と読み替える($d$ は4方向)。たとえば $x\geqq1$ に対し
$$
f_{t+1}(x,0)=f_t(x-1,0)+f_t(x+1,0)+2f_t(x,1),\qquad f_{t+1}(x,x)=2f_t(x,x-1)+2f_t(x+1,x)
$$
であり,軸上と対角線上で係数 $2$ が現れる。時刻 $7$ までの値は次のとおりである(「重み」は代表点の $G$ 軌道に属する点の個数)。
| $(x,y)$ | 重み | $t=0$ | $t=2$ | $t=4$ | $t=6$ |
|---|---|---|---|---|---|
| $(0,0)$ | $1$ | $1$ | $4$ | $36$ | $400$ |
| $(1,1)$ | $4$ | $0$ | $2$ | $24$ | $300$ |
| $(2,0)$ | $4$ | $0$ | $1$ | $16$ | $225$ |
| $(2,2)$ | $4$ | $0$ | $0$ | $6$ | $120$ |
| $(3,1)$ | $8$ | $0$ | $0$ | $4$ | $90$ |
| $(4,0)$ | $4$ | $0$ | $0$ | $1$ | $36$ |
| $(3,3)$ | $4$ | $0$ | $0$ | $0$ | $20$ |
| $(4,2)$ | $8$ | $0$ | $0$ | $0$ | $15$ |
| $(5,1)$ | $8$ | $0$ | $0$ | $0$ | $6$ |
| $(6,0)$ | $4$ | $0$ | $0$ | $0$ | $1$ |
| 重み付き和 | — | $1$ | $16$ | $256$ | $4096$ |
| $(x,y)$ | 重み | $t=1$ | $t=3$ | $t=5$ | $t=7$ |
| :-: | :-: | :-: | :-: | :-: | :-: |
| $(1,0)$ | $4$ | $1$ | $9$ | $100$ | $1225$ |
| $(2,1)$ | $8$ | $0$ | $3$ | $50$ | $735$ |
| $(3,0)$ | $4$ | $0$ | $1$ | $25$ | $441$ |
| $(3,2)$ | $8$ | $0$ | $0$ | $10$ | $245$ |
| $(4,1)$ | $8$ | $0$ | $0$ | $5$ | $147$ |
| $(5,0)$ | $4$ | $0$ | $0$ | $1$ | $49$ |
| $(4,3)$ | $8$ | $0$ | $0$ | $0$ | $35$ |
| $(5,2)$ | $8$ | $0$ | $0$ | $0$ | $21$ |
| $(6,1)$ | $8$ | $0$ | $0$ | $0$ | $7$ |
| $(7,0)$ | $4$ | $0$ | $0$ | $0$ | $1$ |
| 重み付き和 | — | $4$ | $64$ | $1024$ | $16384$ |
$$ f_8(4,0)=f_7(3,0)+f_7(5,0)+2f_7(4,1)=441+49+2\cdot147=784 . $$
$f_7(6,3)$,$f_7(5,4)$ は $\lVert\cdot\rVert_1=9 > 7$ より $0$ であるから
$$
f_8(5,3)=f_7(4,3)+f_7(6,3)+f_7(5,2)+f_7(5,4)=35+0+21+0=56,
$$
$N_8(H)=2\cdot784+4\cdot56=1792$ である。
時刻 $t$ に点 $z$ にいるとき,残り $8-t$ 歩で $H$ に至る移動列の数を $g_t(z)$ とする。最初の一歩で分類して
$$
g_8(z)=\begin{cases}1 & (z\in H)\\ 0 & (z\notin H)\end{cases},\qquad g_t(x,y)=g_{t+1}(x+1,y)+g_{t+1}(x-1,y)+g_{t+1}(x,y+1)+g_{t+1}(x,y-1).
$$
$g_7(z)$ は $z$ の隣接点のうち $H$ に属するものの個数であり,$(4,2)$ の隣接点では $g_7(5,2)=1$(隣接点 $(5,3)$),$g_7(4,3)=1$($(5,3)$),$g_7(4,1)=1$($(4,0)$),$g_7(3,2)=0$ である。よって $g_6(4,2)=1+1+1+0=3$。
補題4
より
$$
|A\cap B|=f_6(4,2)\,g_6(4,2)=15\cdot3=45,\qquad \Pr(A\mid B)=\frac{f_6(4,2)\,g_6(4,2)}{g_0(\mathrm{O})}=\frac{45}{1792}.
$$
ここで $g_0(\mathrm{O})=N_8(H)=1792$ である。
以下は独立の解法とは数えず,既出の解法の表現違いまたは部分的な短縮として扱う。
| 解法 | 主に利用する構造 | 対象 | 範囲 | 長所 | 注意点 |
|---|---|---|---|---|---|
| 本解 | 方向別の回数,境界での最短経路,連結 | 全設問 | 高校 | 問題文からの発想距離が最短,再現性が高い | (1) の3通りの場合分け |
| 3.1 節 | 絶対値の平方差 | $H$ の決定 | 高校 | 点と経路の型を同時に得る | 符号の復元 |
| 3.2 節 | 一歩の母関数の因数分解 | 補題5 | 高校〜大学 | 積公式が一行で従う | 係数比較の正当化(単射性) |
| 3.3 節 | 終点による分解,Bayes の公式 | (3) | 高校 | 分子の内訳が見える | 終点の条件付き分布の重み |
| 別解1 | 斜め座標,独立性 | 全設問 | 高校 | (1)(2) を二項係数の積で一括処理し,$H$ の決定も兼ねる | 独立性の根拠の明示 |
| 参考解1 | 動く軸への条件付け | 全設問 | 高校 | 多項係数を二項係数に分解する | 本解の項の並べ替えにとどまる |
| 参考解2 | 局所遷移,二面体群の対称性 | 全設問 | 高校 | 規則や終点集合の変更に強い | 表の作成に手間がかかる |
試験場での第一選択は本解である。発想の飛躍がなく,(1) から (3) までが同じ計数の延長上にある。別解1は最も構造的であり,(1)(2) を二項係数の積に圧縮し,$H$ の決定も同時に行う。参考解1は本解と計算の原理が近い。参考解2は本問では計算量が多いが,移動規則や終点集合が不規則な問題へそのまま拡張できる。(3) の処理はすべての解法で共通であり,通過時刻の一意化と経路の連結に尽きる。
本問から,「格子上の等確率な歩行について,終点や経由点の条件のもとでの確率を求める」問題に対する探索手順を抽出する。
各解法が,1 節で抽出した構造のどれをどの形で用いるかを横断的に整理する。
| 構造 | 本解 | 別解1 | 参考解1 | 参考解2 |
|---|---|---|---|---|
| 距離と偶奇(補題1) | 用いる | $c_t$ の定義に内蔵 | $c_k$ の定義に内蔵 | 到達不能点を $0$ とする |
| $H$ の決定(補題2) | 因数分解 | $U_8V_8=16$ として同時に処理 | 因数分解 | 因数分解 |
| 符号反転の対称性 | 用いる | $c_t(-u)=c_t(u)$ として | 用いる | 二面体群全体を用いる |
| 境界での最短経路 | 型 II で用いる | $c_8(\pm8)=1$ として | $k=5$ のみとして | 用いない |
| 通過時刻の一意性(補題3) | 用いる | 用いる | 用いる | 用いる |
| 経路の連結(補題4) | 前半 × 後半 | 前半 × 外積表 | 前半 × 後半 | $f_6\cdot g_6$ |
| 独立化(補題5) | 用いない | 中核 | 軸ごとの条件付き独立 | 用いない |
| 症状 | 検討する表現・道具 | 本問での例 |
|---|---|---|
| 終点が到達領域の境界上にある | 最短経路,二項係数一つ | 型 II の点 $(\pm5,\pm3)$ |
| 終点条件が $x\pm y$ で書ける | 斜め座標,独立な二項分布 | (2):$U_8V_8=16$ |
| 二次の不定方程式が終点を与える | 因数分解,偶奇,約数の組 | 補題2,3.1 節 |
| 「いずれかの時刻」の和事象 | 到達可能な時刻の列挙 | 補題3 |
| 経由点と終点の両方の条件 | 経路の連結,終点による分解 | (3),3.3 節 |
| 方向回数の場合分けが増える | 時間分割,母関数 | 参考解1,3.2 節 |
| 終点集合や移動規則が不規則 | 前向き・後ろ向きの漸化式 | 参考解2 |
| 条件付き確率 | 分母の集合の固定,Bayes の公式 | (3),2.3 節 |
補題5
と $(x,y)\leftrightarrow(x+y,\ x-y)$ の対応から,任意の整数 $c\neq0$ と $T\geqq1$ について
$$
\Pr\bigl(X_T^2-Y_T^2=c\bigr)=\frac{1}{4^T}\sum_{\substack{(u,v)\in\mathbb{Z}^2\\ uv=c}}c_T(u)\,c_T(v)
$$
が成り立つ。$c_T(u)\,c_T(v)\neq0$ となるのは $u\equiv v\equiv T\pmod2$,$|u|\leqq T$,$|v|\leqq T$ のときに限るから,和の各項は自動的に格子点に対応する。ここから次が従う。
| 事項 | 高校数学での扱い | 一般理論 |
|---|---|---|
| 経路の計数 | 場合の数,多項係数,二項係数 | 格子路の組合せ論,多項定理 |
| 斜め座標 | 座標の取り替え,独立な試行 | 独立確率変数への分解,部分格子 |
| 経由点 | 条件付き確率,乗法定理 | Markov 性,ランダムウォーク・ブリッジ |
| 漸化式 | 隣接点からの和 | 推移作用素,離散熱方程式 |
| 母関数 | 多項式の展開と係数比較 | Laurent 多項式環,群環,Fourier 解析 |
| $x^2-y^2$ | 因数分解 | 離散調和関数,マルチンゲール |
| 多数歩での挙動 | 扱わない | 局所中心極限定理,再帰性(Pólya) |
本解・別解1・参考解1・参考解2と 3.1〜3.3 節は,いずれも高校数学(場合の数,二項定理,条件付き確率,漸化式)の範囲で完結する。右欄は,それらの計算が成り立つ理由を説明する理論である。
補題5
は,斜め座標での経路数の表 $\bigl(c_t(u)\,c_t(v)\bigr)_{u,v}$ が,パスカルの三角形の第 $t$ 行を位置 $u$ に並べたベクトル $\boldsymbol{c}_t=\bigl(c_t(u)\bigr)_u$ の外積 $\boldsymbol{c}_t\boldsymbol{c}_t^{\top}$,すなわち階数1の行列であることを意味する。元の座標での表は階数1ではない。たとえば $t=1$ の表は
$$
\begin{pmatrix}0&1&0\\ 1&0&1\\ 0&1&0\end{pmatrix}
$$
であり,階数は $2$ である。二次元の計数が一次元の計数二つに完全に分離するのは,適切な座標をとったときに限られる。
三つの計数法(本解・参考解1・別解1)の一致から,組合せ恒等式
$$
\sum_{\substack{e-w=x,\ n-s=y\\ e+w+n+s=t}}\frac{t!}{e!\,w!\,n!\,s!}=\sum_{k=0}^{t}\binom{t}{k}c_k(x)\,c_{t-k}(y)=c_t(x+y)\,c_t(x-y)
$$
が得られる(左辺の和は非負整数 $e,w,n,s$ にわたる)。$x=y=0$,$t=2m$ では $\dfrac{(2m)!}{(j!)^2\bigl((m-j)!\bigr)^2}=\binom{2m}{m}\binom{m}{j}^2$ により,Vandermonde の恒等式 $\sum_j\binom{m}{j}^2=\binom{2m}{m}$ に帰着する。上の恒等式はその2変数版である。
実数 $a,b$($(a,b)\neq(0,0)$)に対し $L(x,y)=ax+by$ とし,一歩での増分を $\Delta L$ とする。
(i) $\Delta L$ のとりうる値がちょうど2個 $\pm\gamma$($\gamma > 0$)であるための必要十分条件は $|a|=|b|$ である。したがって,そのような一次形式は定数倍を除いて $x+y$ と $x-y$ に限られる。
(ii) 方向の確率を $\Pr(\mathsf{E})=\Pr(\mathsf{W})=\frac p2$,$\Pr(\mathsf{N})=\Pr(\mathsf{S})=\frac{1-p}{2}$($0 < p < 1$)とする。このとき $\Delta U$,$\Delta V$ はそれぞれ $\pm1$ を確率 $\frac12$ ずつとるが,$\Delta U$ と $\Delta V$ が独立であるための必要十分条件は $p=\frac12$ である。
(i) $\Delta L\in\lbrace a,-a,b,-b\rbrace$ である。$a=0$ または $b=0$ なら値は $0$ と $\pm b$(または $\pm a$)の3個,$ab\neq0$ かつ $|a|\neq|b|$ なら4個,$|a|=|b|\neq0$ なら2個である。
(ii) $\Delta U=1$ となるのは $\mathsf{E}$,$\mathsf{N}$ のときで,その確率は $\frac p2+\frac{1-p}{2}=\frac12$ である。$\Delta V$ についても同様である。一方 $\Pr(\Delta U=1,\ \Delta V=1)=\Pr(\mathsf{E})=\frac p2$ であり,これが $\frac12\cdot\frac12$ に等しいのは $p=\frac12$ のときに限る。$p=\frac12$ のときは4つの符号の組がいずれも確率 $\frac14$ をもつから,独立である。
斜め座標は,移動規則から系統的に探せる唯一の候補であり,ひらめきに頼らずに見つかる。また独立性は,格子が正方形であることだけでなく,4方向が等確率であることにも依存する。
$\mathbb{Z}^d$ の単純ランダムウォークの一歩は $2d$ 通り,$d$ 個の $\pm1$ の組は $2^d$ 通りであり,$2d=2^d$ となるのは $d=1,2$ に限る。4方向を符号の組に一対一に対応させる本問の仕組みは,$d=2$ に特有である。$d=2$ では
補題5
と Stirling の公式から
$$
\Pr(\mathrm{P}_{2m}=\mathrm{O})=\Bigl(\binom{2m}{m}2^{-2m}\Bigr)^2\sim\frac{1}{\pi m}\qquad(m\to\infty)
$$
が直ちに従い,$\sum_m\Pr(\mathrm{P}_{2m}=\mathrm{O})=\infty$ から原点への再帰性が得られる(Pólya の再帰定理の $d=2$ の場合)。$d=3$ では対応する級数は収束し,歩行は非再帰的である。
補題6
は,終点を固定した歩行(ランダムウォーク・ブリッジ)の時刻 $s$ での分布を与える。斜め座標では,$\mathrm{P}_T=w$ という条件は二つの符号列の和を $w$ の斜め座標 $(w_u,w_v)$ に固定する条件であり,この条件のもとでも二つの符号列は独立である(それぞれ和を固定した列の全体の上で一様)。一次元のブリッジの時刻 $s$ の位置は超幾何分布に従い
$$
\Pr\Bigl(\sum_{i\leqq s}\varepsilon_i=h\ \Big|\ \sum_{i\leqq T}\varepsilon_i=u\Bigr)=\frac{c_s(h)\,c_{T-s}(u-h)}{c_T(u)}
$$
である。したがって二次元のブリッジの通過確率は,二つの超幾何確率の積になる。本問では
$$
\Pr\bigl(\mathrm{P}_6=(4,2)\mid \mathrm{P}_8=(4,0)\bigr)=\frac{c_6(6)\,c_2(-2)}{c_8(4)}\cdot\frac{c_6(2)\,c_2(2)}{c_8(4)}=\frac{1}{28}\cdot\frac{15}{28}=\frac{15}{784},
$$
$$
\Pr\bigl(\mathrm{P}_6=(4,2)\mid \mathrm{P}_8=(5,3)\bigr)=\frac{c_6(6)\,c_2(2)}{c_8(8)}\cdot\frac{c_6(2)\,c_2(0)}{c_8(2)}=1\cdot\frac{30}{56}=\frac{15}{28}
$$
であり,
3.3 節
の値を再現する。
関数 $f:\mathbb{Z}^2\to\mathbb{R}$ に対し
$$
(Mf)(x,y)=\frac14\bigl(f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1)\bigr)
$$
とおく。このとき
$$
M(x^2-y^2)=x^2-y^2,\qquad M(xy)=xy,\qquad M(x^2+y^2)=x^2+y^2+1 .
$$
したがって $X_t^2-Y_t^2$,$X_tY_t$,$X_t^2+Y_t^2-t$ はマルチンゲールであり,$\mathbb{E}[X_t^2-Y_t^2]=\mathbb{E}[X_tY_t]=0$,$\mathbb{E}[X_t^2+Y_t^2]=t$ が成り立つ。
$\frac14\bigl((x+1)^2+(x-1)^2+2x^2\bigr)=x^2+\frac12$ と,$y$ についての同じ式から,第1式と第3式を得る。$\frac14\bigl((x+1)y+(x-1)y+x(y+1)+x(y-1)\bigr)=xy$ から第2式を得る。各時刻の移動がそれまでの経過によらず等確率であるから $\mathbb{E}\bigl[f(\mathrm{P}_{t+1})\mid\mathrm{P}_0,\ldots,\mathrm{P}_t\bigr]=(Mf)(\mathrm{P}_t)$ であり,後半が従う。
双曲線の族 $x^2-y^2=c$ は,離散調和多項式の等高線である。斜め座標では $x^2-y^2=uv$,$xy=\frac{u^2-v^2}{4}$,$x^2+y^2=\frac{u^2+v^2}{2}$ であり,$uv$ のマルチンゲール性は $U,V$ の増分の独立性と平均 $0$ から,$x^2+y^2-t$ のマルチンゲール性は $U_t^2-t$,$V_t^2-t$ のマルチンゲール性から直ちに従う。ただし期待値の情報は点確率を決めない。$\Pr(X_8^2-Y_8^2=16)$ を求めるには分布そのもの,すなわち 補題5 が必要である。
一歩の母関数 $F(z,w)=z+z^{-1}+w+w^{-1}$ は群環 $\mathbb{Z}[\mathbb{Z}^2]\cong\mathbb{Z}[z^{\pm1},w^{\pm1}]$ の元であり,経路数は $F^t$ の係数である(
3.2 節
)。単位円上 $z=e^{i\theta}$,$w=e^{i\varphi}$ に制限すると,一歩の特性関数
$$
\phi(\theta,\varphi)=\frac14F(e^{i\theta},e^{i\varphi})=\frac{\cos\theta+\cos\varphi}{2}=\cos\frac{\theta+\varphi}{2}\,\cos\frac{\theta-\varphi}{2}
$$
を得る。積への分離は $(a+a^{-1})(b+b^{-1})$ への因数分解の解析的な表現であり,双対変数 $\frac{\theta\pm\varphi}{2}$ が斜め座標に対応する。
作用素の言葉では,一次元の推移作用素を $(L\psi)(n)=\frac12\bigl(\psi(n+1)+\psi(n-1)\bigr)$ とすると,
命題9
の $M$ は元の座標で
$$
M=\frac12\bigl(L\otimes I+I\otimes L\bigr)
$$
と表される。これは $L\otimes L$ ではない($L\otimes L$ は斜めの4方向に動く歩行の作用素である)。斜め座標 $(u,v)$ に移り,状態空間を $u\equiv v\pmod 2$ の部分格子に制限すると
$$
M=L\otimes L
$$
となり,$M^t=L^t\otimes L^t$ が
補題5
の作用素版である。テンソル積への分離には座標の取り替えが本質的に必要であり,元の座標のまま $M=L\otimes L$ とする記述は誤りである。
確率 $p_t(z)=f_t(z)/4^t$ は
$$
p_{t+1}(z)-p_t(z)=\frac14\sum_{d}\bigl(p_t(z-d)-p_t(z)\bigr)
$$
をみたす($d$ は4方向)。右辺は離散 Laplace 作用素であり,これは離散熱方程式である。
補題5
と一次元の局所中心極限定理
$$
\Pr(U_t=u)=\sqrt{\frac{2}{\pi t}}\;e^{-u^2/(2t)}\bigl(1+o(1)\bigr)\qquad(u\equiv t\ (\mathrm{mod}\ 2),\ u=O(\sqrt{t}))
$$
から,$u^2+v^2=2(x^2+y^2)$ により,$x+y\equiv t\pmod2$ の点で
$$
p_t(x,y)=\frac{2}{\pi t}\,e^{-(x^2+y^2)/t}\bigl(1+o(1)\bigr)
$$
を得る。$t=8$,$(x,y)=(4,0)$ では主要項は $\frac{1}{4\pi}e^{-2}\approx0.0108$ であり,正確な値 $\frac{49}{4096}\approx0.0120$ に近い。一方,境界上の $(5,3)$ では主要項 $\approx0.00114$ に対し正確な値は $\frac{56}{65536}\approx0.00085$ であり,分布の裾では近似は粗い。有限歩の厳密な点確率には組合せ的な計数が適切である。
「ランダムウォーク」の語は,K. Pearson が1905年に Nature 誌に寄せた問題に由来する。格子上の単純ランダムウォークの再帰性は G. Pólya が1921年の論文(街路網における酔歩を扱ったもの)で示した。$d=2$ の再帰性の標準的な証明には, 補題5 と同じ平方の形 $\binom{2m}{m}^2$ が現れる。差分方程式と酔歩の関係は Courant–Friedrichs–Lewy(1928)の差分法の研究にも現れ,マルチンゲールの理論は J. L. Doob(1953年の著書)により体系化された。二項係数の畳み込みの公式は Vandermonde(18世紀)の名で呼ばれるが,朱世傑(1303年)にすでに現れる。本問は,これらの理論が交わる最も小さな具体例の一つになっている。