跳到主要内容

中央大学 理工学研究科 情報工学専攻 2026年2月実施 一般入試（春季）問題III

标签：

Author​

祭音Myyura (Based on 中央大学の公式解答例 refined with GPT 6 Astra)

Description​

問題 I は必答。問題 II～V のうち、2 問を選んで解答すること。

問題 III.

以下の性質が成り立っているような離散型確率変数 XX を考える：任意の k∈N={1,2,3,…}k\in\mathbb{N}=\{1,2,3,\ldots\} に対し、

Pr⁡(X=k)=0.999k−11000.\Pr(X=k)=\frac{0.999^{k-1}}{1000}.
  1. Pr⁡(X>k)\Pr(X>k) を k=0,1,2,…k=0,1,2,\ldots に対し求めよ。
  2. XX の期待値 E[X]\mathbb{E}[X] を求めよ。
  3. Pr⁡(X>1001∣X>1000)\Pr(X>1001\mid X>1000) を求めよ。

今、ある問題 Π\Pi と、それを解くアルゴリズムの設計を考える。

  1. 問題 Π\Pi に対し、計算時間 TT 以内に正しい解を確率 δ\delta で出力するアルゴリズム AA が存在するとする (0<δ≤1)(0<\delta\leq1)。また、出力の正当性は tt 時間以内で検証できるとする。ここで、検証手続きは常に正しく、正しい解は必ず受理され、誤った解は必ず棄却されるものとする。問題 Π\Pi に対し、確率 11 で正しい解を出力するアルゴリズム BB を（AA を用いて）設計せよ。また BB の計算時間の期待値（の上界）を求めよ。

  2. Π\Pi は最大化問題であると仮定する。即ち、各入力に対して実数値を返す目的関数が与えられており、その最大値を求める問題である（例：ナップサック問題、最大カット問題、…）。

    問題 Π\Pi に対し、計算時間 TT 以内に確率 ϵ\epsilon (0<ϵ<1)(0<\epsilon<1) で最大値を返すアルゴリズム AA が存在するとする（ここで、残りの確率 1−ϵ1-\epsilon では最大値でない実数値を出力するとする）。任意の数 0<δ<10<\delta<1 に対し、最大値を 1−δ1-\delta 以上の確率で返すアルゴリズム BB を（AA を用いて）設計せよ。また BB の計算時間の上界を求めよ。

题目描述​

问题 I 为必答题；从问题 II～V 中选择 2 题作答。

问题 III

设离散型随机变量 XX 满足：对于任意 k∈N={1,2,3,…}k\in\mathbb{N}=\{1,2,3,\ldots\}，

Pr⁡(X=k)=0.999k−11000.\Pr(X=k)=\frac{0.999^{k-1}}{1000}.
  1. 对 k=0,1,2,…k=0,1,2,\ldots，求 Pr⁡(X>k)\Pr(X>k)。
  2. 求 XX 的期望 E[X]\mathbb{E}[X]。
  3. 求 Pr⁡(X>1001∣X>1000)\Pr(X>1001\mid X>1000)。

下面考虑某个问题 Π\Pi 及求解它的算法设计。

  1. 假设存在算法 AA，它在时间 TT 内以概率 δ\delta 输出问题 Π\Pi 的正确解，其中 0<δ≤10<\delta\leq1。输出的正确性可以在时间 tt 内验证，且验证过程始终正确：正确解一定被接受，错误解一定被拒绝。利用 AA 设计一个以概率 11 输出正确解的算法 BB，并求其运行时间期望的上界。

  2. 假设 Π\Pi 为最大化问题，即给定一个对各输入返回实数值的目标函数，要求其最大值，例如背包问题、最大割问题等。假设算法 AA 在时间 TT 内以概率 ϵ\epsilon（0<ϵ<10<\epsilon<1）返回最大值，以其余概率 1−ϵ1-\epsilon 输出一个不等于最大值的实数。对于任意 0<δ<10<\delta<1，利用 AA 设计一个以至少 1−δ1-\delta 的概率返回最大值的算法 BB，并给出运行时间的上界。

Kai​

1. 裾確率​

XX は成功確率 p=0.001p=0.001 の幾何分布である。等比級数を用いると、

Pr⁡(X>k)=∑j=k+1∞0.999j−11000=0.001⋅0.999k1−0.999=0.999k.\Pr(X>k)=\sum_{j=k+1}^{\infty}\frac{0.999^{j-1}}{1000} =\frac{0.001\cdot0.999^k}{1-0.999} =\boxed{0.999^k}.

k=0k=0 の場合も Pr⁡(X>0)=1\Pr(X>0)=1 となる。

2. 期待値​

正の整数値を取る確率変数の裾和公式より、

E[X]=∑k=0∞Pr⁡(X>k)=∑k=0∞0.999k=1000.\mathbb{E}[X]=\sum_{k=0}^{\infty}\Pr(X>k) =\sum_{k=0}^{\infty}0.999^k =\boxed{1000}.

3. 条件付き確率​

{X>1001}⊂{X>1000}\{X>1001\}\subset\{X>1000\} だから、

Pr⁡(X>1001∣X>1000)=0.99910010.9991000=0.999.\Pr(X>1001\mid X>1000) =\frac{0.999^{1001}}{0.999^{1000}} =\boxed{0.999}.

これは幾何分布の無記憶性にも対応する。

4. 検証を伴う反復​

各回に新しい独立な乱数を用いて、次を繰り返す。

  1. AA を実行する。
  2. 出力を検証し、受理されたらその解を返して終了する。棄却されたら次の回へ進む。

終了時の解は検証済みなので必ず正しい。rr 回連続して棄却される確率は (1−δ)r(1-\delta)^r であり、これは r→∞r\to\infty で 00 になる。従って確率 11 で停止し、正しい解を返す。

試行回数 NN は成功確率 δ\delta の幾何分布に従うので、E[N]=1/δ\mathbb{E}[N]=1/\delta。各回の時間は高々 T+tT+t であるから、

E[time⁡(B)]≤T+tδ.\boxed{\mathbb{E}[\operatorname{time}(B)]\leq\frac{T+t}{\delta}}.

「確率 11 で停止する」ことは、有限の最悪実行時間を保証することとは異なる。δ=1\delta=1 なら 1 回で必ず終了する。

5. 成功確率の増幅​

最大化問題の近似解を返すという通常の解釈に従い、各出力は実行可能解の目的関数値であり、真の最大値 MM を超えないものとする。また各回の実行では独立な乱数を使う。

AA を kk 回実行し、出力を Y1,…,YkY_1,\ldots,Y_k として、max⁡jYj\max_jY_j を返す。少なくとも 1 回 MM が出力されれば全体の出力も MM になるため、失敗確率は

Pr⁡(max⁡jYj≠M)=(1−ϵ)k.\Pr(\max_jY_j\ne M)=(1-\epsilon)^k.

従って

k=⌈log⁡δlog⁡(1−ϵ)⌉=⌈log⁡1/(1−ϵ)1δ⌉k=\left\lceil\frac{\log\delta}{\log(1-\epsilon)}\right\rceil =\left\lceil\log_{1/(1-\epsilon)}\frac1\delta\right\rceil

とすれば、成功確率は 1−(1−ϵ)k≥1−δ1-(1-\epsilon)^k\geq1-\delta となる。AA の実行にかかる総時間は高々

T⌈log⁡δlog⁡(1−ϵ)⌉.\boxed{T\left\lceil\frac{\log\delta}{\log(1-\epsilon)}\right\rceil}.

出力の最大値を更新する比較も数えると追加時間は O(k)O(k) であり、全体は O(k(T+1))O(k(T+1)) である。

なお、問題文の「最大値でない実数値」が MM より大きい値も許すと解釈すると、この増幅法は保証できない。例えば失敗時に常に M+1M+1 を返すなら、反復の最大値が MM になる確率は ϵk\epsilon^k に下がる。従って、上の解法には「失敗時も MM 以下の実行可能な値を返す」という条件が必要であり、任意の誤った実数出力を許す条件だけからは、この成功確率の保証は導けない。

Reference​

本页目录