跳到主要内容

東京大学 情報理工学研究科 2022年8月実施 数学 第3問

标签：

Author​

hari64boli64, 祭音Myyura

Description​

丸石 ◯\bigcirc と四角い石 □\square をランダムに左から右に一直線上に一つずつ並べる。 0<q<10 < q < 1 として、丸石を確率 1−q1 - q、四角い石を確率 qq で独立同一分布に従って並べていく。 MM を正の整数として、四角い石が MM 個連続して並べられた直後に並べることを停止する。 M=4M = 4 の場合の例を以下に示す。

  • 列 11 ◯□□□□\bigcirc\square\square\square\square
  • 列 22 □◯□◯◯□□□□\square\bigcirc\square\bigcirc\bigcirc\square\square\square\square

停止後の石の数を表す確率変数を LL とする。 上に示した列の場合、列 11 と列 22 はそれぞれ L=5L = 5、L=9L = 9 となる。

並べている途中の状態を考える。kk を非負整数とし、右端から四角い石が kk 個連続している状態を CkC_k とする。例えば、M=4M = 4 の時に以下の列を考える。

  • 列 33 ◯□□□◯◯□□\bigcirc\square\square\square\bigcirc\bigcirc\square\square
  • 列 44 □◯□◯◯\square\bigcirc\square\bigcirc\bigcirc

M=4M = 4 の場合を考えているため、列 33 と列 44 はまだ停止していない。 列 33 は右端から四角い石が 22 個連続しているので状態 C2C_2 である。 列 44 は右端に四角い石がないので状態 C0C_0 である。 状態 CkC_k から nn 個石を並べたときに初めて停止条件を満たす確率を akna_{kn} とする。ここで nn は非負整数である。 akna_{kn} に対して以下のような母関数 Ak(t)A_k(t) を定義する。

Ak(t)=∑n=0∞tnaknA_k(t) = \sum_{n=0}^{\infty} t^n a_{kn}

この時、以下の問いに答えよ。

(1) M=1M = 1 の時、LL の平均と分散を求めよ。

(2) Ak(t)A_k(t) が満たす漸化式を求めよ。

(3) Ak(t)A_k(t) を q,M,t,kq, M, t, k を用いて表せ。

(4) LL の平均を求めよ。

题目描述​

从左到右独立地逐个放置圆石和方石：圆石概率为 1−q1-q，方石概率为 qq，其中 0<q<10<q<1。给定正整数 MM，一旦出现连续 MM 个方石便立即停止。 令停止时已放置的石头总数为随机变量 LL。

在尚未停止时，若末尾恰有 kk 个连续方石，则称状态为 CkC_k。从状态 CkC_k 起再放置 nn 个石头时首次满足停止条件的概率记为 akna_{kn}，并定义概率母函数

Ak(t)=∑n=0∞tnakn.A_k(t)=\sum_{n=0}^{\infty}t^na_{kn}.

回答下列问题。

（1）当 M=1M=1 时，求 LL 的均值和方差。

（2）求 Ak(t)A_k(t) 满足的递推关系。

（3）用 q,M,t,kq,M,t,k 显式表示 Ak(t)A_k(t)。

（4）求一般 MM 下 LL 的均值。

Kai​

(1)​

M=1M=1 の場合、四角い石が出た時点で操作は停止される。

よって、状態 C0C_0 から nn 個石を並べたときに初めて停止条件を満たす確率 a0na_{0n} は、

a0n={0(n=0)(1−q)n−1q(n≥1)\begin{aligned} a_{0n} = \begin{cases} 0 & (n = 0 ) \\ (1-q)^{n-1}q & (n \geq 1) \end{cases} \end{aligned}

となる。

よって、

E[L]=∑n=0∞na0n=∑n=1∞n(1−q)n−1q=qddt(∑n=1∞tn)t=1−q=qddt(t1−t)t=1−q=q1(1−(1−q))2=1q\begin{aligned} \mathbb{E}[L] & = \sum_{n=0}^{\infty} na_{0n} \\ & = \sum_{n=1}^{\infty} n(1-q)^{n-1}q \\ & = q\frac{\text{d}}{\text{d}t}\left(\sum_{n=1}^{\infty}{t^n}\right)_{t=1-q} \\ & = q\frac{\text{d}}{\text{d}t}\left(\frac{t}{1-t}\right)_{t=1-q} \\ & = q\frac{1}{(1-(1-q))^2} \\ & = \frac{1}{q} \\ \end{aligned}
V[L]=E[L2]−E[L]2=∑n=0∞n2a0n−1q2=∑n=1∞n2(1−q)n−1q−1q2=2−qq2−1q2=1−qq2\begin{aligned} \mathbb{V}[L] & = \mathbb{E}[L^2] - \mathbb{E}[L]^2 \\ & = \sum_{n=0}^{\infty} n^2a_{0n} - \frac{1}{q^2} \\ & = \sum_{n=1}^{\infty} n^2(1-q)^{n-1}q - \frac{1}{q^2} \\ & = \frac{2-q}{q^2}-\frac{1}{q^2} \\ & = \frac{1-q}{q^2} \\ \end{aligned}

となる。

(参考: これは幾何分布と呼ばれる分布である)

(2)​

まず、状態 Ck(k>M)C_k(k>M) は定義されない事に注意する。

また、状態 Ck(k=M)C_k(k=M) の場合、既に操作は停止しているので、ak0=1a_{k0}=1 より、Ak(t)=1A_k(t)=1 となる。

k<Mk<M の場合を考える。この時、状態遷移図は次のようになる。

状態 C_k から、四角い石なら確率 q で C_(k+1)、丸石なら確率 1-q で C_0 に移る。

この図に示した通り、

  • 確率 qq で四角い石が出る時、1個石を並べた上で、状態 Ck+1C_{k+1} に遷移する。
  • 確率 1−q1-q で丸石が出る時、1個石を並べた上で、状態 C0C_0 に遷移する。

という関係性があるので、

Ak(t)=qtAk+1(t)+(1−q)tA0(t)(0≤k<M)\begin{aligned} A_k(t)=qtA_{k+1}(t)+(1-q)tA_0(t) \quad (0 \leq k < M) \end{aligned}

となる。あるいは、同じことだが、

AM−i(t)=qtAM−i+1(t)+(1−q)tA0(t)(0<i≤M)\begin{aligned} A_{M-i}(t)=qtA_{M-i+1}(t)+(1-q)tA_0(t) \quad (0 < i \leq M) \end{aligned}

となる。

(なお、答えの書き方は色々あると思うが、恐らく上式のいずれかだけで十分だと思う。)

(3)​

(2) の結果より、

AM−1(t)=qtAM(t)+(1−q)tA0(t)=qt+(1−q)tA0(t)AM−2(t)=qtAM−1(t)+(1−q)tA0(t)=qt(qt+(1−q)tA0(t))+(1−q)tA0(t)=q2t2+(1−q)qt2A0(t)+(1−q)tA0(t)=q2t2+((1−q)qt2+(1−q)t)A0(t)AM−3(t)=qtAM−2(t)+(1−q)tA0(t)=qt(q2t2+((1−q)qt2+(1−q)t)A0(t))+(1−q)tA0(t)=q3t3+((1−q)q2t3+(1−q)qt2+(1−q)t)A0(t)\begin{aligned} A_{M-1}(t) & =qtA_{M}(t)+(1-q)tA_0(t) \\ & =qt+(1-q)tA_0(t) \\ A_{M-2}(t) & =qtA_{M-1}(t)+(1-q)tA_0(t) \\ & =qt\left(qt+(1-q)tA_0(t)\right)+(1-q)tA_0(t) \\ & =q^2t^2+(1-q)qt^2A_0(t)+(1-q)tA_0(t) \\ & =q^2t^2+\left((1-q)qt^2+(1-q)t \right)A_0(t) \\ A_{M-3}(t) & =qtA_{M-2}(t)+(1-q)tA_0(t) \\ & =qt\left(q^2t^2+\left((1-q)qt^2+(1-q)t\right)A_0(t)\right)+(1-q)tA_0(t) \\ & =q^3t^3+\left((1-q)q^2t^3+(1-q)qt^2+(1-q)t\right)A_0(t) \\ \end{aligned}

となっていく。

つまり、

AM−i(t)=qiti+(∑j=0i−1(1−q)qjtj+1)A0(t)=(qt)i+(1−q)t(∑j=0i−1(qt)j)A0(t)=(qt)i+(1−q)t(1−(qt)i1−qt)A0(t)(0<i≤M)\begin{aligned} A_{M-i}(t) & =q^it^i+\left(\sum_{j=0}^{i-1}(1-q)q^{j}t^{j+1}\right)A_0(t) \\ & =(qt)^i+(1-q)t\left(\sum_{j=0}^{i-1}(qt)^{j}\right)A_0(t) \\ & =(qt)^i+(1-q)t\left(\frac{1-(qt)^i}{1-qt}\right)A_0(t) \quad (0 < i \leq M) \end{aligned}

となる。

特に、i=Mi=M の場合を考えると、

A0(t)=(qt)M+(1−q)t(1−(qt)M1−qt)A0(t)\begin{aligned} A_0(t) = (qt)^M+(1-q)t\left(\frac{1-(qt)^M}{1-qt}\right)A_0(t) \\ \end{aligned}

整理して、

A0(t)=(qt)M1−(1−q)t(1−(qt)M1−qt)=(1−qt)(qt)M1−t+t(1−q)(qt)MAM−i(t)=(qt)i+(1−q)t(1−(qt)i1−qt)(1−qt)(qt)M1−t+t(1−q)(qt)M(0<i≤M)=(qt)i1−t+t(1−q)(qt)M−i1−t+t(1−q)(qt)M(0<i≤M)Ak(t)=(qt)M−k1−t+t(1−q)(qt)k1−t+t(1−q)(qt)M(0≤k<M)\begin{aligned} A_0(t) & =\frac{(qt)^M}{1-(1-q)t\left(\frac{1-(qt)^M}{1-qt}\right)} = \frac{(1-qt)(qt)^M}{1-t+t(1-q)(qt)^M} \\ A_{M-i}(t) & =(qt)^i+(1-q)t\left(\frac{1-(qt)^i}{1-qt}\right)\frac{(1-qt)(qt)^M}{1-t+t(1-q)(qt)^M} \quad (0 < i \leq M) \\ & = (qt)^i \frac{1-t+t(1-q)(qt)^{M-i}}{1-t+t(1-q)(qt)^M} \quad (0 < i \leq M) \\ A_{k}(t) & =(qt)^{M-k} \frac{1-t+t(1-q)(qt)^{k}}{1-t+t(1-q)(qt)^M} \quad (0 \leq k < M) \\ \end{aligned}

となる。

(4)​

(3) の結果より、

A0(t)=(1−qt)(qt)M1−t+t(1−q)(qt)M\begin{aligned} A_0(t) =\frac{(1-qt)(qt)^M}{1-t+t(1-q)(qt)^M} \end{aligned}

である。

MM 個ずつの互いに重ならないブロックを考えると、各ブロックがすべて四角い石となる確率は qM>0q^M>0 であり、ブロック間は独立である。よって LL は平均 M/qMM/q^M の待ち時間で上から抑えられ、E[L]<∞\mathbb E[L]<\infty となる。

(1) と同様の考え方から、答えは (ddtA0(t))t=1\left(\frac{\text{d}}{\text{d}t}A_0(t)\right)_{t=1} である。

よって、これを微分して、代入整理すると、

1−qM(1−q)qM\begin{aligned} \frac{1-q^M}{(1-q)q^M} \end{aligned}

となる。

(なお、M=1M=1を代入すると、これは 1q\frac{1}{q} となり、(1) の結果に一致する)

本页目录