方針
正方形の頂点を対角同士と隣接同士で分けて考える。(1)(2) は偶数ステップ後だけ に戻れることと,偶数ステップ後には対角の2点に等確率でいることを使う。(3) 以降は2点が消滅しない限り常に対角の位置に戻ることに注目し,各ステップで消滅する確率が で一定であることから生存確率と平均寿命を求める。
解答
(1)
点 は1ステップごとに隣の頂点へ移動するので,奇数ステップ後には の隣の頂点 のどちらかにあり, にはいない。したがって が奇数のとき である。
偶数ステップ後には は または にいる。2ステップ後を考えると, に戻る経路は の2通り, に行く経路も の2通りで,いずれも等確率である。したがって偶数ステップ後には に等確率でいる。よってである。
(2) が奇数のとき, も も にはいないので確率は0である。 が偶数のとき,(1)より である。また は から出発するが,同じ理由で偶数ステップ後には に等確率でいるから である。2点の移動は互いに独立なので である。したがってである。
(3)
点が消滅していないとき,2点は常に対角の位置にある。たとえば が にいるとき,次のステップで両方が に移るか,両方が に移れば消滅する。この確率は である。残りの確率 では,2点は という対角の位置に移り,消滅しない。他の対角の組からでも同じである。
したがって,各ステップで,それまで存在していた点が次も存在する確率は である。よって ステップ後にも点が存在する確率は である。
(4)
点の寿命が であるとは, ステップ後までは存在し, ステップ後に消滅することである。その確率は である。したがって平均寿命は である。 とおくとである。ここで に を入れると である。よって平均寿命は である。
別解
解法2
方針
1点の位置は2ステップごとの2状態遷移で処理する。消滅問題は2点の相対位置を
「対角」か「消滅」かの2状態にまとめ、生存確率の尾和から平均寿命を求める。
解答
(1)
奇数ステップ後には は 、偶数ステップ後には にいる。
2ステップごとに のどちらから出ても、次の はそれぞれ確率 である。
よって(2)
は独立に移動する。奇数 では両者とも にいない。
偶数 ではそれぞれ確率 で にいるから(3)
生存中の2点は常に対角にいる。次の1歩で同じ頂点を選んで消滅する確率は である。
異なる頂点を選べば再び対角にいる。よって 歩後の生存確率は
である。
(4)
寿命を とする。 であることは、 ステップ後まで生存することと同値なので である。
非負整数値の平均を尾確率で足すと
総評
難度は10段階中5、計算量は10段階中4。前半は偶奇、後半は生存中の2点が常に対角にある不変量が核心である。(3)は生存率、(4)は寿命の尾確率の和で検算できる。