MathLabs

競技数学と問題解決

オリンピック不等式

競技数学における不等式証明の中核ツール:AM–GM–HM a1+⋯+ann≥a1⋯ann\frac{a_1+\dots+a_n}{n} \ge \sqrt[n]{a_1\cdots a_n}、コーシー・シュワルツ (∑ai2)(∑bi2)≥(∑aibi)2\left(\sum a_i^2\right)\left(\sum b_i^2\right) \ge \left(\sum a_i b_i\right)^2 とその相棒であるティツの補題 ∑ai2bi≥(∑ai)2∑bi\sum \frac{a_i^2}{b_i} \ge \frac{(\sum a_i)^2}{\sum b_i}、並べ替え不等式、チェビシェフ、イェンゼン、そしてシューアの不等式 ar(a−b)(a−c)+br(b−a)(b−c)+cr(c−a)(c−b)≥0a^r(a-b)(a-c) + b^r(b-a)(b-c) + c^r(c-a)(c-b) \ge 0。∑(ait−bi)2≥0\sum(a_i t - b_i)^2 \ge 0 の判別式によるコーシー・シュワルツの完全な証明と、r=1r=1 のシューアの不等式の証明を与え、これらの道具を信号対雑音比の限界とカルバック・ライブラー情報量に応用する。

直観平均はなぜそのように振る舞うのか

2つの正の数、例えば 44 と 99 を考える。その算術平均は 4+92=6.5\frac{4+9}{2}=6.5 だが、幾何平均は 4⋅9=6\sqrt{4\cdot 9}=6 である。幾何平均は常に小さい(2数が等しいときは等しい)——等しくない2数を掛け合わせるために押し込めると、足し合わせるときより多くを「失う」。この単純な観察を nn 個の数に一般化し、いくつかの仲間の不等式(コーシー・シュワルツ、並べ替え、チェビシェフ、イェンゼン、シューア)と組み合わせたものが、競技数学者がある代数式が常に別の式以上であることを証明するために使う道具箱のすべてである——無限個の場合を探索するように見えるものを、数行のきれいな代数に変える。

AM-GMの差を下向き放物線として可視化する関数グラフ
4,94,9 の算術平均 6.56.5 と幾何平均 66 の差を曲線として描く:調整して f(x)=−x2+13f(x) = -x^2+13 がAM–GMの差 (a+b2)2−ab=(a−b2)2≥0\left(\frac{a+b}{2}\right)^2 - ab = \left(\frac{a-b}{2}\right)^2 \ge 0 をどう可視化するか見てみよう。

中高AM–GM–HMとコーシー・シュワルツ

定義: 3つの平均の比較

正の実数 a1,…,ana_1,\dots,a_n について、算術平均は a1+⋯+ann\frac{a_1+\dots+a_n}{n}、幾何平均は a1⋯ann\sqrt[n]{a_1\cdots a_n}、調和平均は n1a1+⋯+1an\frac{n}{\frac{1}{a_1}+\dots+\frac{1}{a_n}} である。AM–GM–HM の連鎖は算術 ≥\ge 幾何 ≥\ge 調和を主張し、等号が全体で成り立つのはちょうど a1=⋯=ana_1=\dots=a_n のときである。

a1+⋯+ann≥a1⋯ann≥n1a1+⋯+1an\frac{a_1+\dots+a_n}{n} \ge \sqrt[n]{a_1\cdots a_n} \ge \frac{n}{\frac{1}{a_1}+\dots+\frac{1}{a_n}}

コーシー・シュワルツはこの考えを内積へと鋭くする:(∑ai2)(∑bi2)≥(∑aibi)2\left(\sum a_i^2\right)\left(\sum b_i^2\right) \ge \left(\sum a_i b_i\right)^2。直接の系であるティツの補題(エンゲル形式)は競技の分数式にしばしばより便利である:∑ai2bi≥(∑ai)2∑bi\sum \frac{a_i^2}{b_i} \ge \frac{(\sum a_i)^2}{\sum b_i}、これはコーシー・シュワルツに ai→ai/bia_i \to a_i/\sqrt{b_i}、bi→bib_i \to \sqrt{b_i} を代入して得られる。

∑ai2bi≥(∑ai)2∑bi\sum \frac{a_i^2}{b_i} \ge \frac{(\sum a_i)^2}{\sum b_i}
どの不等式を使うか
道具最も適する場面
AM–GM積と和の比較、和一定の最適化
コーシー・シュワルツ / ティツ分数の和、内積の限界
並べ替え / チェビシェフ順序付き数列の積の和
イェンゼン平均の凸/凹関数
シューア対称な3変数不等式

大学完全な証明:コーシー・シュワルツとシューア

定理: コーシー・シュワルツの不等式

実数 a1,…,ana_1,\dots,a_n と b1,…,bnb_1,\dots,b_n について:(∑ai2)(∑bi2)≥(∑aibi)2\left(\sum a_i^2\right)\left(\sum b_i^2\right) \ge \left(\sum a_i b_i\right)^2、等号成立は数列が比例するとき、かつそのときに限る。

なぜ正しいのか?

この一つの不等式(とそのエンゲル形式の系であるティツの補題)は、オリンピック不等式問題における最も有用な道具であり、分数や積の和を扱いやすい限界に変換する。

証明

ステップ1:補助的な二次式を立てる。 実変数 tt と式 ∑i=1n(ait−bi)2\sum_{i=1}^n (a_i t - b_i)^2 を考える。これは実数の平方の和なので、任意の実数 tt について常に ≥0\ge 0 である:∑(ait−bi)2≥0\sum(a_i t - b_i)^2 \ge 0。

**ステップ2:tt の二次式に展開する。** 展開すると ∑(ait−bi)2=t2∑ai2−2t∑aibi+∑bi2\sum (a_i t - b_i)^2 = t^2 \sum a_i^2 - 2t \sum a_i b_i + \sum b_i^2。A=∑ai2A = \sum a_i^2、B=∑aibiB = \sum a_i b_i、C=∑bi2C = \sum b_i^2 とおくと、式は任意の実数 tt について At2−2Bt+C≥0At^2 - 2Bt + C \ge 0 となる。

ステップ3:退化した場合を扱う。 A=0A = 0 なら全ての ai=0a_i = 0 であり、示すべき不等式 B2≤ACB^2 \le AC の両辺は 00 なので、不等式は自明に成り立つ(等号成立)。

**ステップ4:A>0A > 0 のとき判別式を用いる。** 正の主係数 AA を持つ二次式 At2−2Bt+CAt^2 - 2Bt + C が任意の実数 tt について ≥0\ge 0 であるとき、実根は高々1つしか持てないため、判別式は正になり得ない:(2B)2−4AC≤0(2B)^2 - 4AC \le 0、すなわち 4B2≤4AC4B^2 \le 4AC、すなわち B2≤ACB^2 \le AC。

ステップ5:結論。 代入し戻すと (∑aibi)2≤(∑ai2)(∑bi2)\left(\sum a_i b_i\right)^2 \le \left(\sum a_i^2\right)\left(\sum b_i^2\right) となり、これがまさに (∑ai2)(∑bi2)≥(∑aibi)2\left(\sum a_i^2\right)\left(\sum b_i^2\right) \ge \left(\sum a_i b_i\right)^2 である。等号成立は判別式がゼロ、すなわち二次式が実の重根 t0t_0 を持つとき、すなわち全ての ii について ait0=bia_i t_0 = b_i のとき——数列 (ai)(a_i) と (bi)(b_i) が比例するとき——に限る。

定理: シューアの不等式(r=1r=1)

非負実数 a,b,ca,b,c について:a(a−b)(a−c)+b(b−a)(b−c)+c(c−a)(c−b)≥0a(a-b)(a-c)+b(b-a)(b-c)+c(c-a)(c-b)\ge 0、等号成立は a=b=ca=b=c、または3つのうち2つが等しく残り1つが 00 のとき、かつそのときに限る。

なぜ正しいのか?

シューアの不等式は、AM–GMやコーシー・シュワルツに直接抵抗する対称な3変数の競技不等式、特に a+b+ca+b+c、ab+bc+caab+bc+ca、abcabc を同時に含むものに対する標準的な決め手である。

証明

ステップ1:対称性による簡約。 式 a(a−b)(a−c)+b(b−a)(b−c)+c(c−a)(c−b)a(a-b)(a-c)+b(b-a)(b-c)+c(c-a)(c-b) は a,b,ca,b,c について対称なので、一般性を失うことなく a≥b≥c≥0a \ge b \ge c \ge 0 と仮定する。

ステップ2:最初の2項をまとめる。 a(a−b)(a−c)+b(b−a)(b−c)=(a−b)[a(a−c)−b(b−c)]a(a-b)(a-c) + b(b-a)(b-c) = (a-b)\big[a(a-c) - b(b-c)\big] とまとめ、両項から共通因子 (a−b)(a-b) をくくり出す(b(b−a)(b−c)=−(a−b)⋅b(b−c)b(b-a)(b-c) = -(a-b)\cdot b(b-c) に注意)。

ステップ3:括弧内を簡約する。 a(a−c)−b(b−c)=a2−ac−b2+bc=(a2−b2)−c(a−b)=(a−b)(a+b)−c(a−b)=(a−b)(a+b−c)a(a-c) - b(b-c) = a^2 - ac - b^2 + bc = (a^2-b^2) - c(a-b) = (a-b)(a+b) - c(a-b) = (a-b)(a+b-c) と展開する。

ステップ4:結合する。 代入し戻すと、まとめた項は (a−b)⋅(a−b)(a+b−c)=(a−b)2(a+b−c)(a-b)\cdot(a-b)(a+b-c) = (a-b)^2(a+b-c) に等しい。したがって式全体は (a−b)2(a+b−c)+c(a−c)(b−c)(a-b)^2(a+b-c) + c(a-c)(b-c) に等しい(最後の項はまさに元の第3項そのまま)。

ステップ5:各部分の符号を確認する。 a≥b≥c≥0a \ge b \ge c \ge 0 なので:(a−b)2≥0(a-b)^2 \ge 0 は常に成り立つ。a+b−ca+b-c の符号については、a≥ca \ge c なので a−c≥0a - c \ge 0、かつ b≥0b \ge 0 なので a+b−c=(a−c)+b≥0a+b-c = (a-c)+b \ge 0。よって (a−b)2(a+b−c)≥0(a-b)^2(a+b-c) \ge 0。第2の部分については:c≥0c \ge 0、a−c≥0a-c \ge 0(a≥ca\ge c なので)、b−c≥0b - c \ge 0(b≥cb \ge c なので)であり、c(a−c)(b−c)≥0c(a-c)(b-c) \ge 0 は非負の3数の積である。

ステップ6:結論。 式全体は2つの非負項の和 (a−b)2(a+b−c)+c(a−c)(b−c)≥0(a-b)^2(a+b-c) + c(a-c)(b-c) \ge 0 であり、r=1r=1 のシューアの不等式が証明された。等号成立には両方が消える必要がある:a=ba=b(第1項を 00 にする)かつ c(a−c)(b−c)=0c(a-c)(b-c)=0(さらに a=ca=c なら a=b=ca=b=c を、c=0c=0 なら a=b,c=0a=b, c=0 を強制する)、これは述べた等号条件と一致する。

発展実世界での応用と具体例

コーシー・シュワルツは単なる競技の技ではない:信号処理では、信号とマッチドフィルタの相関を限界づけ、マッチドフィルタ受信機で達成可能な最大の信号対雑音比(SNR)を与える。情報理論では、イェンゼンの不等式(凸関数 −log⁡-\log に適用)がカルバック・ライブラー情報量 DKL(P∥Q)=∑pilog⁡piqiD_{KL}(P\|Q) = \sum p_i \log\frac{p_i}{q_i} が常に ≥0\ge 0 であること(ギブスの不等式)を証明し、これはKL情報量を確率分布間の(非対称ではあるが)有効な距離尺度たらしめる基礎的事実であり、交差エントロピーのような機械学習の損失関数の中心をなす。

例: コーシー・シュワルツによるマッチドフィルタSNR限界

受信機は i=1,…,ni=1,\dots,n について yi=si+niy_i = s_i + n_i を観測する。ここで sis_i は既知の信号、nin_i は ∑ni2≤N\sum n_i^2 \le N を満たす雑音である。受信機は相関 ∑siyi\sum s_i y_i を計算する。コーシー・シュワルツを用いて、この相関を雑音がどれだけ乱しうるか、すなわち ∣∑sini∣|\sum s_i n_i| を限界づけよ。

解答

ステップ1:コーシー・シュワルツを数列 (si)(s_i) と (ni)(n_i) に直接適用する:(∑sini)2≤(∑si2)(∑ni2)\left(\sum s_i n_i\right)^2 \le \left(\sum s_i^2\right)\left(\sum n_i^2\right)。

ステップ2:雑音エネルギー限界 ∑ni2≤N\sum n_i^2 \le N を代入し、信号エネルギーを Es=∑si2E_s = \sum s_i^2 と書く:(∑sini)2≤Es⋅N\left(\sum s_i n_i\right)^2 \le E_s \cdot N。

ステップ3:平方根を取る:∣∑sini∣≤EsN|\sum s_i n_i| \le \sqrt{E_s N}。一方、雑音のない相関はまさに ∑si2=Es\sum s_i^2 = E_s であるから、最悪ケースの相対的な乱れは EsNEs=N/Es\frac{\sqrt{E_s N}}{E_s} = \sqrt{N/E_s} となる——信号エネルギー EsE_s が雑音エネルギー NN に比べて大きいほど小さくなり、これはまさにSNR(比 Es/NE_s/N)が検出信頼性を制御するという直感的な主張であり、コーシー・シュワルツはマッチドフィルタ sis_i が実は最適な相関器であることを示す(他のどんなフィルタもより弱い限界しか与えない)、なぜなら等号成立は雑音がちょうど sis_i 自身に比例するときにのみ起こるからである。

例: イェンゼンによるKL情報量の非負性証明

確率分布 p1,…,pnp_1,\dots,p_n と q1,…,qnq_1,\dots,q_n(すべて正で和は 11)について、ギブスの不等式 DKL(P∥Q)=∑ipilog⁡piqi≥0D_{KL}(P\|Q) = \sum_i p_i \log\frac{p_i}{q_i} \ge 0 を証明せよ。

解答

ステップ1:DKL(P∥Q)=−∑ipilog⁡qipi=∑ipi⋅(−log⁡qipi)D_{KL}(P\|Q) = -\sum_i p_i \log\frac{q_i}{p_i} = \sum_i p_i \cdot \left(-\log\frac{q_i}{p_i}\right) と書き換え、これが pip_i で重み付けされた期待値 Ep[−log⁡qipi]\mathbb{E}_{p}\left[-\log \frac{q_i}{p_i}\right] であると認識する。

ステップ2:−log⁡-\log は凸関数なので、イェンゼンの不等式は任意の確率変数 XX について E[−log⁡X]≥−log⁡E[X]\mathbb{E}[-\log X] \ge -\log \mathbb{E}[X] を与える(ここで X=qi/piX = q_i/p_i、確率 pip_i)。

ステップ3:E[X]=∑ipi⋅qipi=∑iqi=1\mathbb{E}[X] = \sum_i p_i \cdot \frac{q_i}{p_i} = \sum_i q_i = 1 を計算する、qiq_i が確率分布をなすからである。

ステップ4:組み合わせると DKL(P∥Q)=E[−log⁡X]≥−log⁡E[X]=−log⁡1=0D_{KL}(P\|Q) = \mathbb{E}[-\log X] \ge -\log \mathbb{E}[X] = -\log 1 = 0 となり、DKL(P∥Q)≥0D_{KL}(P\|Q) \ge 0 が証明される。等号成立は全ての ii について qi/piq_i/p_i が定数のとき、かつそのときに限る(狭義凸関数 −log⁡-\log に対するイェンゼンの等号条件による)、すなわち P=QP = Q のときである。

∑(ait−bi)2≥0\sum(a_i t - b_i)^2 \ge 0 の判別式によるコーシー・シュワルツの証明において、B2≤ACB^2 \le AC を結論づけるために使われる二次式 At2−2Bt+CAt^2-2Bt+C のどんな性質が使われるか?

シューアの不等式 a(a−b)(a−c)+b(b−a)(b−c)+c(c−a)(c−b)≥0a(a-b)(a-c)+b(b-a)(b-c)+c(c-a)(c-b)\ge 0 が(a=b=ca=b=c 以外で)等号成立するのはどんな a,b,ca,b,c の値か?

ティツの補題 ∑ai2bi≥(∑ai)2∑bi\sum \frac{a_i^2}{b_i} \ge \frac{(\sum a_i)^2}{\sum b_i} はコーシー・シュワルツからどんな代入により導かれるか?

DKL(P∥Q)≥0D_{KL}(P\|Q) \ge 0 というギブスの不等式の証明で、凸関数 −log⁡-\log に適用される不等式はどれか?

参考文献

  1. J. Michael Steele (2004). The Cauchy-Schwarz Master Class
  2. Radmila Bulajich Manfrino, José Antonio Gómez Ortega, Rogelio Valdez Delgado (2009). Inequalities: A Mathematical Olympiad Approach
  3. Thomas M. Cover, Joy A. Thomas (2006). Elements of Information Theory