T.2 · Discrete mathematics, probability and numerical methods

大学卒GRE準備。検証済みETS範囲内の地域的な目標；これは独自の教育であり、公式テストや得点予測器ではありません。

前提知識: 有限の計数、初等確率、再帰式と微分法。

• 計数法、再帰式、グラフ論的推論および論理を用いること
• 確率と分布の性質を計算すること
• 数値近似を適用し、誤差を評価すること

再帰式: シリーズ項をその前の項に結びつける規則。

排反: 同時に発生することができない事象。

まず計数モデルを選択する: r 個の異なる対象の順列は n(n−1)⋯(n−r+1) で、無順序部分集合は C(n,r) である。n 頂点の完全単純グラフでは、無順序な頂点ペアごとに辺が一つあり、n(n−1)/2 本の辺となる。ループや重複辺があればモデルが変わる。平面内の一般位置にある n 本の直線について、k 本目の直線はそれ以前の k−1 本の直線を異なる点で交差し、k 領域を追加する。総数は 1+n(n+1)/2 であり、平行線や三線一点会合则有則那么这个计数不成立。

少なくとも一度の出現を数えるために補集合を用い、非還元抽出後の実際の残存標本に対して条件付き確率を考える。n 個の等確率値から r 個の i.i.d. 結果を選ぶとき、すべてが異なる確率は r≤n の場合 n(n−1)⋯(n−r+1)/n^r である。その補集合は重複する結果を数える。N 回の独立試行で成功確率 p が一定の二項分布において、平均は Np、分散は Np(1−p) である。確率が等しいだけでは独立性を証明できない。

再帰式は前期の値から後期の値を記述し、シリーズを決定するために十分な初期データが必要である。添字と値を分離せよ: a_n=2a_(n−1) かつ a_0=3 ならば a_n=3·2^n となる。グラフやアルゴリズムの議論では、新しい頂点またはステップが何を追加するかを特定することで再帰式を導出することがある。閉じた公式は再帰式と初期条件の両方を満たすべきであり、いくつかの観測された項に当てはめただけではすべての添字について証明にならない。

数値近似には誤差の根拠が必要である。二分割法は連続関数の符号変換区間を維持し、各ステップで幅を半分にするが、连续性が破綻すれば零点が存在しない場合がある。ニュートンの更新式は x_new=x−f(x)/f′(x) であり、現在の点で導関数がゼロでないことが必要である。全ての初期値から収束するわけではない。近似の残留値と x における誤差は異なる。表示された余剰の桁数を精度として扱うのではなく、手法の仮定と停止基準を明記せよ。

f(x)=x²−2 および x₀=1 のとき、ニュートンのステップは 1−(1−2)/2=1.5 を与える。次の値は 1.5−0.25/3=1.4167 となる。これらは sqrt(2) の近似値だが、f′(0)=0 であるため、ゼロは有効ではない初期点となる。

正の確率を持つ事象は、独立でありながら排反であることはできない。

5 種類の記号から、放回抽選により4つのラベル付き抽出を行う。少なくとも2つの抽出が一致する確率を求めよ。4 個の異なる記号の順列選択と無順序選択の数を比較せよ。

解例

同等の確率を持つ順列抽出文字列は $5^4$ 通り存在する。重複のない文字列の数は $5\cdot4\cdot3\cdot2=120$ 通りである。

順列での無重複選択は 120 通り、無順序部分集合は $\binom54=5$ 通りである。各部分集合は $4!=24$ 通りの順序で現れる。$4!$ で割るのは無順序の数に対してのみ適切であり、抽出確率の分母としては不適切である。

$[1,2]$ 上で $f(x)=x^3-2$ に対し二分法を適用せよ。最初の2つの残された括弧と、10回の二分法後の中間点誤差の上限を答える。単なる符号の変化だけで、$[-1,1]$ 上で $1/x$ に対する二分法の正当性が保証されるか？

解答後の確認

多項式は連続であり、$f(1)<0<f(2)$。最初の中点は $1.5$ で正の値を持ち、$[1,1.5]$ を保持する。次の中点は $1.25$ で負の値を持ち、$[1.25,1.5]$ を保持する。 10 回の半減後、幅は $2^{-10}$ となり、その保持区間の中心値は括弧で囲まれた根と最大でも $2^{-11}=1/2048$ しか異ならない。誤差の上限は区間に基づき、単なる小さな残留値 alone ではない。 $1/x$において、ゼロは特異点であり根は存在しない。区間内での連続性が成立せず、端点の符号が異なってもこの手法を正当化できない。