東京大学 新領域創成科学研究科 複雑理工学専攻 2011年8月実施 専門基礎科目 第4問

标签：

• Tokyo-University
• First-Return-Time-of-One-Dimensional-Random-Walk
• Reflection-Principle
• Catalan-Number

Author

犬 (finalized by 祭音Myyura with assistance from GPT 6 Astra)

Description

粒子は時刻 $t=0$ に $x=0$ にあり、時刻が 1 進むごとに $x$ 軸上を確率 $p$ で $+1$、確率 $1-p$ で $-1$ 移動する。$0<p<1$ とする。

問1

$t=2$ に $x=0$ にいる確率を求めよ。

問2

$t=2m$ に $x=0$ にいる確率を $\alpha(m)$ とする。ただし $m$ は非負整数である。

(a) 粒子の動きを下図のように $(t,x)$ 平面の経路で表す。$(0,0)$ から $(2m,0)$ までの経路の個数を求めよ。

(b) $\alpha(m)$ を求めよ。

問3

再び $(t,x)$ 平面で経路を考える。

(a) $(1,1)$ から $(2m-1,1)$ までの経路の個数を求めよ。

(b) $(1,-1)$ から $(2m-1,1)$ までの経路の個数を求めよ。

(c) (a) の経路のうち $x=0$ を経由するものの個数が、(b) の個数と等しいことを証明せよ。

(d) $(0,0)$ から $(2m,0)$ までの経路のうち、途中で $x=0$ を経由しないものの個数を求めよ。

問4

$t=2m$ にはじめて $x=0$ に戻る確率を $\beta(m)$ とする。$m$ は正整数である。

(a) $\beta(m)$ を求めよ。

(b) $\beta(m)=4p(1-p)\alpha(m-1)-\alpha(m)$ を証明せよ。

题目描述

粒子在 $t=0$ 时位于 $x=0$，每个时间步以概率 $p$ 向右移动 1，以概率 $1-p$ 向左移动 1，$0<p<1$。

问1 求 $t=2$ 时位于原点的概率。

问2 记 $t=2m$ 时位于原点的概率为 $\alpha(m)$，$m$ 为非负整数。（a）把粒子的运动表示为 $(t,x)$ 平面中的路径（如上图），求从 $(0,0)$ 到 $(2m,0)$ 的路径数。（b）求 $\alpha(m)$。

问3 （a）求 $(1,1)$ 到 $(2m-1,1)$ 的路径数。（b）求 $(1,-1)$ 到 $(2m-1,1)$ 的路径数。（c）证明（a）中经过 $x=0$ 的路径数等于（b）的路径数。（d）求从 $(0,0)$ 到 $(2m,0)$、途中不经过 $x=0$ 的路径数。

问4 记首次在 $t=2m$ 返回原点的概率为 $\beta(m)$，$m$ 为正整数。（a）求 $\beta(m)$。（b）证明 $\beta(m)=4p(1-p)\alpha(m-1)-\alpha(m)$。

Kai

問1

左右、右左の二通りがあるので $\boxed{2p(1-p)}$。

問2

(a) $2m$ 歩のうち上向き $m$ 歩を選ぶから $\boxed{\binom{2m}{m}}$。

(b) 各経路の確率は $p^m(1-p)^m$。従って

$$\boxed{\alpha(m)=\binom{2m}{m}[p(1-p)]^m},\qquad\alpha(0)=1.$$

問3

$m\ge1$ とし、下添字が範囲外の二項係数は零とする。

(a) $2m-2$ 歩のうち上向きは $m-1$ 歩なので、$\boxed{\binom{2m-2}{m-1}}$。

(b) 上向きは $m$ 歩、下向きは $m-2$ 歩なので、$\boxed{\binom{2m-2}{m-2}}$。

(c) $(1,1)$ から出発して初めて $x=0$ に達する時刻までの部分を $x=0$ に関して反射する。これにより $(1,-1)$ から終点までの経路を得る。逆に、後者は必ず $x=0$ に達するので、最初の到達までを反射すれば元に戻る。従って全単射である。

(d) 最初に上へ進む場合は (a) から (b) を引き、最初に下へ進む場合も同数。従って

$$\boxed{2\left[\binom{2m-2}{m-1}-\binom{2m-2}{m-2}\right] =\frac2m\binom{2m-2}{m-1}}.$$

問4

(a) 問3(d)の経路はすべて右左それぞれ $m$ 歩なので

$$\boxed{\beta(m)=\frac2m\binom{2m-2}{m-1}[p(1-p)]^m}.$$

(b) $q=p(1-p)$ とおく。$\binom{2m}{m}=(4-2/m)\binom{2m-2}{m-1}$ より

$$4q\alpha(m-1)-\alpha(m) =\left[4\binom{2m-2}{m-1}-\binom{2m}{m}\right]q^m =\frac2m\binom{2m-2}{m-1}q^m=\beta(m).$$