ユークリッドの互除法

概要

ユークリッドの互除法(Euclidean Algorithm)は、2つの自然数の最大公約数を求める手順。

2つの自然数a, b \; (a \ge b)の最大公約数(GCD: greatest common divisor)は、bと剰余r = a \mod bの最大公約数に等しいという性質を利用。数を順次割り込んでいき、剰余がゼロとなったときの除数が最大公約数となる。

(1)   }\begin{align*}a \mod b &= r_1 \quad (a \ge b) \\b \mod r &= r_2 \\&\vdots \\r_{n-1} \mod r_n &= 0 \\&\Downarrow \\\gcd(a, b) &= r_n\end{align*}

証明

以下の余りあり除算を考える。

(2)   \begin{gather*}a \mod b = r \Rightarrow a = bd + r\end{gather*}

a, bの公約数をmとすると、上式は以下のように変形され、mは余りrの公約数でもあることがわかる。

(3)   \begin{gather*}a = mp , \quad b = mq \\r = mp - mqd = m(p - qd)\end{gather*}

一方、b, rの公約数をnとすると、naの公約数であることがわかる。

(4)   \begin{gather*}b = ns , \quad r = nt \\a = nsd + nt = n(sd + t)\end{gather*}

これより、a, bの公約数の集合とb, rの公約数の集合は等しく、最大公約数も等しくなる。

(5)   \begin{equation*}a = bd+r \Rightarrow \gcd(a, b) = \gcd(b, r)\end{equation*}

計算例

143と91の最大公約数を求める。

(6)   \begin{align*}&143 \mod 91 = 52 \\&91 \mod 52 = 39 \\&52 \mod 39 = 13 \\&39 \mod 13 = 0 \\&\therefore \gcd(143, 91) = 13\end{align*}

再帰関数による実装

PythonとCLispの再帰関数による実装例は以下の通り。ただし、第1引数>第2引数を前提としており、エラー処理はしていない。

Python

CLisp

 

最大公約数・最小公倍数

約数

約数の定義

整数Nの約数(divisor, factor)とは、Nを割り切る整数(余りが生じない除数)。

整数mNの約数であるとき、m|Nと表し、ある整数aに対してN=maが成り立つことでもある。一般には自然数あるいは0以上の整数で考える。

通常はm \ne 0の条件を課すが、0も含める場合は、N=0の時に限り0が約数になる。

例えば12の約数は、以下の6個。

(1)   \begin{align*}&12 \div 1 = 12 \\&12 \div 2 = 6 \\&12 \div 3 = 4 \\&12 \div 4 = 3 \\&12 \div 6 =2 \\&12 \div 12 = 1\end{align*}

効率的な約数の求め方

m|Nであるとき、\frac Nm|Nである。これよりm = \frac Nmとして、\sqrt N以下の約数m_iを求め、あとはN/m_iを計算すれば、手間が半分で済む。

Nが平方数の場合は\sqrt Nも約数となり、約数の総数は奇数個、平方数でない場合は偶数異なる。

0、1の約数

0の約数は0 = maとなる整数mであり、0以上の全ての整数である。

1の約数は1 = maとなる整数mであり、1のみ。

1は全ての整数の約数。

素数の約数

素数の定義が「1と自身以外に約数を持たない数」なので、約数は2個。

公約数

2つの数の公約数は、それらの最大公約数の約数。

0、1との公約数

aと1の公約数は1のみ。

aと0の公約数は、aの約数全て(0の約数は0以上の全ての整数)。

公約数と剰余

a \mod b = rのとき、a, bの公約数はb, rの公約数でもある。

最大公約数

2つの数の最大公約数(greatest common divisor)を、\gcd(a, b)のように表す。

最大公約数を求める手順として、にユークリッドの互除法がある。

0、1との最大公約数

(2)   \begin{gather*}\gcd(a, 0) = a \\\gcd(a, 1) = 1\end{gather*}

最大公約数と剰余

被除数と除数の最大公約数は、除数と剰余の最大公約数でもある。

(3)   \begin{equation*}a \mod b = r \Rightarrow \gcd(a, b) = \gcd(b, r)\end{equation*}

倍数

倍数(multiple)とは、ある数a(整数に限らない)を整数倍した数である。

*** QuickLaTeX cannot compile formula:
\begin{gather}\cdots -3a, -2a, -a, 0, a, 2a, 3a, \cdots\betin{gather}

*** Error message:
\begin{gather} on input line 8 ended by \end{document}.
leading text: \end{document}
Undefined control sequence \betin.
leading text: \end{document}
Undefined control sequence \betin.
leading text: \end{document}
Emergency stop.

  • 0の倍数は0のみ
  • 0はすべての数の倍数
  • すべての数は自分自身の倍数
  • すべての整数は1と-1の倍数

最小公倍数

最小公倍数(least common multiple)とは、2つの整数の公倍数のうち、正で最小のもの。

たとえば36と56の最小公倍数は504。

最大公約数と最小公倍数の積

2つの数a, bの積は、それらの最大公約数と最小公倍数の積に等しい。

(4)   \begin{equation*}ab = \gcd(a, b) \cdot \operatorname{lcm}(a, b)\end{equation*}

 

Python3 – mathモジュール

使い方

数学関数を使うためのモジュールで、importし、各定数・関数について、math.[定数名・関数名]として使う。

関数群

主なもの

定数

pi, e
円周率、自然対数の底
inf
浮動小数点の正の無限大。負の無限大は-math.inf。
nan
浮動小数点の非数NaN。

数論関数

ceil(x)
xの天井(x以上の最小の整数)。
floor(x)
xの床(x以下の最大の整数)。
fabs(x)
xの絶対値。
fmod(x, y)
x \mod yを返す。浮動小数点の場合はx % yよりこちらを使う。
gcd(x, y)
xとyの最大公約数。gcd(0.0, 0.0)は0を返す。
isfinite(x)
xが無限でもNaNでもない時にTrueを返す。
ifinf(x)
xが正の無限大か負の無限大の時にTrueを返す。
isnan(x)
xがNaNの時にTrueを返す。

指数・対数関数

sqrt(n)
nの平方根
pow(x, y)
xのy乗(x^y)。pow(1.0, x)、pow(x, 0.0)は常に1.0を返す。
exp(x)
e^x
expm1(n)
e^x - 1。桁落ちに対して最大精度で計算。
log2(x), log10(x), log(x [,b])
それぞれ2、10、bを底とする対数関数。3番目の関数でbを省略した場合は自然対数\ln x
log1p(x)
1+\log x

を返す。ゼロに近いxに対して正確になるよう計算される。

三角関数

sin(x), cos(x), tan(x)
三角関数。
asin(x), acos(x), atan(x)
逆三角関数
atan2(y, x)
[latex]\tan^{^1}を返すが、4つの象限に対する符号から、[latex]-\pi \sim \pi[/lates]の値を返す。
degrees(r), radians(d)
ラジアンから度、度からラジアンへの変換。

 

剰余と合同式

商と剰余

剰余(余り)について

a \div bの商がq、余りがrのとき、以下のように表される。d:divisor、q:quotient、r:reminderの意味。

(1)    \begin{eqnarray*} &a = dq + r \\ &a \mod d = r \end{eqnarray*}

余りの定義を「割る数未満の自然数あるいは0」とすると、

(2)    \begin{eqnarray*} 8 &=& 3 \times 2 + 2 \\ 7 &=& 3 \times 2 + 1 \\ 6 &=& 3 \times 2 + 0 \\ 5 &=& 2 \times 2 + 2 \\ 4 &=& 2 \times 2 + 1 \\ 3 &=& 2 \times 2 + 0 \end{eqnarray*}

割られる数が負の場合には、

(3)    \begin{eqnarray*} -9 &=& 3 \times (-3) + 0 \\ -8 &=& 3 \times (-3) + 1 \\ -7 &=& 3 \times (-3) + 2 \\ -6 &=& 3 \times (-2) + 0 \\ -5 &=& 3 \times (-2) + 1  \\ -4 &=& 3 \times (-2) + 2 \end{eqnarray*}

割る数が負の場合には、

(4)    \begin{eqnarray*} 9 &=& -3 \times (-3) + 0 \\ 8 &=& -3 \times (-3) + 1 \\ 7 &=& -3 \times (-3) + 2 \\ 6 &=& -3 \times (-2) + 0 \\ 5 &=& -3 \times (-2) + 1 \\ 4 &=& -3 \times (-2) + 2 \\ \end{eqnarray*}

負数の余り

余りとして負の数を認めることもできる。ただしその場合、商と余りの組み合わせが1つとは限らない。

(5)    \begin{eqnarray*} 10 &=& -3 \times (-3) + 1 \\ 10 &=& -3 \times (-4) -2 \end{eqnarray*}

余りの定義(要件)は以下の2通りがあり、いずれを採用するかは任意。

  • 余りを割る数の絶対値より小さい0以上とする(0 \le r < |d|)
  • 余りの絶対値が割る数の絶対値より小さい数とする(0 \le |r| < |d|)

特別な場合の余り

割る数が1あるいは-1のときは、余りは常に0。

(6)    \begin{eqnarray*} a &=& 1 \times a + 0 \\ a &=& -1 \times (-a) + 0 \end{eqnarray*}

割られる数が1のときの余りは1、割られる数が-1なら余りは割る数の絶対値から1を現じた値(余りを正と定義した場合)。

(7)    \begin{eqnarray*} 1 &=& b \times 0 + 1 \\ -1 &=& b \times 1 + b - 1 \quad (b > 0) \\ -1 &=& b \times (-1)1 + (-b - 1) \quad (b < 0) \end{eqnarray*}

合同式

合同式の定義

整数a, bを正の整数dで割った余りが等しいとき、以下のように表記し、「a, bdを法として合同である」という。

(8)    \begin{eqnarray*} a &\equiv& b \mod{d}\\ a &\equiv& b \pmod d \end{eqnarray*}

これは次のようにも表現できる。

(9)    \begin{equation*} a - pd = b - qd = r \end{equation*}

合同式の例

(10)    \begin{eqnarray*} 7 &\equiv& 4 \bmod 3\\ 6 &\equiv& 4 \bmod 2\\ 6 &\equiv& 0 \bmod 2\\ 5 &\equiv& 1 \bmod 2 \\ 5 &\equiv& (-1) \bmod 3 \end{eqnarray*}

合同式の性質

以下、合同式の\mod dを省略する。

合同式の和

(11)    \begin{equation*} a_1 \equiv b_1 , \;  a_2\equiv b_2 \; \Rightarrow \; a_1 + a_2 \equiv b_1 + b_2 \end{equation*}

【証明】

 \begin{eqnarray} a_1 - p_1 d &=& b_1 - q_1 d \\ a_2 - p_2 d &=& b_2 - q_2 d \\ &\Downarrow& \\ (a_1 + a_2) - (p_1 + p_2)d &=& (b_1 + b_2) - (q_1 + q_2) d

合同式の積

(12)    \begin{equation*} a_1 \equiv b_1 , \;  a_2\equiv b_2 \; \Rightarrow \; a_1 a_2 \equiv b_1 b_2 \end{equation*}

【証明】

(13)    \begin{eqnarray*} a_1 - p_1 d &=& b_1 - q_1 d \\ a_2 - p_2 d &=& b_2 - q_2 d \\ &\Downarrow& \\ (a_1 - p_1 d)(a_2 - p_2 d) &=& (b_1 - q_1 d)(b_2 - q_2 d) \\ &\Downarrow& \\ a_1 a_2 - (a_1 p_2 + a_2 p_1 + p_1 p_2 d) d &=& b_1 b_2 - (b_1 q_2 + b_2 q_1 + q_1 q_2 d) d \end{eqnarray*}

合同式の商

a, \; dが互いに素(a \perp d)のとき、以下が成り立つ。

(14)    \begin{equation*} ab \equiv ac \bmod d \; \Rightarrow \; b \equiv c \bmod d \quad ( {\rm where} \; a \perp d ) \end{equation*}

【証明】

(15)    \begin{eqnarray*} ab \equiv ac \bmod d \; &\Rightarrow& \; ab = dp + r , \; ac = dq + r \\ &\Rightarrow& a(b - c) = d(p + q) \\ \end{eqnarray*}

ここでa, \; bは互いに素なので、b-cdの倍数となる。

(16)    \begin{eqnarray*} b - c = dk &\Rightarrow& \; b = dm + s , \; ac = dn + s \\ &\Rightarrow& b \equiv c \bmod d \\ \end{eqnarray*}

合同式の冪乗

(17)    \begin{equation*} a \equiv b \bmod d \; \Rightarrow \; a^n \equiv b^n \bmod d \end{equation*}

【証明】

(18)    \begin{equation*} a \equiv b \bmod d \quad \Leftrightarrow \quad \left\{ \begin{array}{l} a = pd + r \\ b = qd + r \end{array} \right. \end{equation*}

(19)    \begin{eqnarray*} a^n &=& (pd + r)^n = \sum_{k=0}^n \dbinom{n-k}{k} (pd)^{n-k} r^k \\ &=& pd \sum_{k=0}^{n-1} \dbinom{n-k}{k} (pd)^{n-k-1} r^k + r^n \\ b^n &=& (qd + r)^n = \sum_{k=0}^n \dbinom{n-k}{k} (qd)^{n-k} r^k \\ &=& qd \sum_{k=0}^{n-1} \dbinom{n-k}{k} (qd)^{n-k-1} r^k + r^n \end{array} \end{eqnarray*}

 

二項定理

二項定理の表現

(1)    \begin{align*} (x + y)^n &= \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k \\ &= x^n + n x^{n-1}y + \cdots + \binom{n}{k} x^k y^{n-k} + \cdots + y^n \end{align*}

具体例

(2)    \begin{align*} (x + y)^2 &= x^2 + 2xy + y^2 \\ (x + y)^3 &= x^3 + 3x^2 y +3x y^2 + x y^3 \\ (x + y)^4 &= x^4 + 4x^3 y + 6x^2 y^2 + 4x y^3 + y^4 \end{align*}

証明

数学的帰納法で証明する。

n = 0のとき、

(3)    \begin{equation*} (x + y)^0 = \binom 00 x^0 y^0 = 1 \end{equation*}

n = 1のとき、

(4)    \begin{equation*} (x + y)^1 = \binom 10 x^1 y^0 + \binom 11 x^0 y^1 = x + y \end{equation*}

ここでn-1のときに以下が成り立つとする。

(5)    \begin{equation*} (x + y)^{n-1} = \sum_{k=0}^{n-1} \binom{n-1}{k} x^{n-1-k} y^k \end{equation*}

このときnに関しては、

(6)    \begin{eqnarray*} (x + y)^n &=& (x + y) \sum_{k=0}^{n-1} \binom {n-1}{k} x^{n-1-k} y^k \\ &=& \sum_{k=0}^{n-1} \binom {n-1}{k} (x^{n-k} y^k + x^{n-1-k} y^{k+1}) \end{eqnarray*}

これを右辺は以下のように展開できる。

 \begin{array}{rrrrrrrrrrrrrrr} & x^n & + & (n-1) x^{n-1} y & \cdots & \binom{n-1}{k} x^{n-k} y^k & \cdots & x y^{n-1} \\ + &&& x^{n-1} y & \cdots & \binom{n-1}{k-1} x^{n-k} y^k &\cdots & (n-1) x y^{n-1} & + & y^n \\ \hline & x^n & + & n x^{n-1} y & \cdots & \left( \binom{n-1}{k} - \binom{n-1}{k-1}\right) x^{n-k}{k} & \cdots & n x y^{n-1} & + & y^n \\ \end{array} \\

(7)    \begin{eqnarray*} \binom{n-1}{k} - \binom{n-1}{k-1} &=& \frac{(n-1)!}{(n-k-1)! k!} - \frac{(n-1)!}{(n-k)! (k-1)!} \\ &=& (n-1)! \frac{(n-k) - k}{(n-k)! k!} = \binom nk \end{eqnarray*}

これより、n \ge 0に対して(1)が証明された。

パスカルの三角形

数のような数による三角形をパスカルの三角形(Pascal’s triangle)と呼び、n行目の数の列が二項展開のn乗の係数となっている。

各項の計算の仕方は、一つ上の段の左右の数の和として求めていく(左端・右端の外側はゼロと考える)。

pascals-triangle

パスカルの三角形の各項が二項展開の計数となること、すなわちm段目のn項目の数をa_{m \cdot n}とし、これが\binom{m-1}{n-1}となることを、数学的帰納法で証明する。

(8)    \begin{eqnarray*} a_{2 \cdot 1} &=& \binom{1}{0} = 1 \\ a_{2 \cdot 2} &=& \binom{1}{1} = 1 \end{eqnarray*}

(9)    \begin{eqnarray*} a_{m \cdot n} &=& a_{m-1 \cdot n-1} + a_{m-1 \cdot n} = \binom{m-2}{n-2} + \binom{m-2}{n-1} \\ &=& \frac{(m-2)!}{(m-n)!(n-2)!} + \frac{(m-2)!}{(m-n-1)!(n-1)!} \\ &=& (m-2)! \frac{(n-1) + (m-n)}{(m-n)!(n-1)!} = \frac{(m-1)!}{(m-n)!(n-1)!} \\ &=& \binom{m-1}{n-1} \end{eqnarray*}

 

ロシアンルーレットの確率

基本

ロシアンルーレットは、賭の順番問題や条件付き確率の問題としてよく見かける。まず、一番基本的なルールで考える。

1人の相手とロシアンルーレットで命をかけることになった。6発入りの拳銃に1発だけ弾を込め、最初にシリンダーを高速で回転させる。シリンダーが止まったところで、相手と交互に引き金を引いていくとして、まず自分から始めるのと相手に譲るのと、どちらが生き残る可能性が高いか。

 

n回目に実弾に当たる確率をP_n \; (n = 1~6)とすると、

1発目で当たる確率は、6つの弾倉のどこかに実弾が入っているので、

(1)    \begin{equation*} P_1 = \frac{1}{6} \end{equation*}

2発目で当たる確率は、1発目で実弾に当たらず、2発目は残り5つの弾倉のどこかに実弾が入っているので、

(2)    \begin{equation*} P_2 = \frac{5}{6} \times \frac{1}{5} = \frac{1}{6} \end{equation*}

以下、6発目まで同じように考えて、

(3)    \begin{eqnarray*} P_3 &=& \frac{5}{6} \times \frac{4}{5} \times \frac{1}{4} = \frac{1}{6} \\ P_4 &=& \frac{5}{6} \times \frac{4}{5} \times \frac{3}{4} \times \frac{1}{3} = \frac{1}{6} \\ P_5 &=& \frac{5}{6} \times \frac{4}{5} \times \frac{3}{4} \times \frac{2}{3} \times \frac{1}{2} = \frac{1}{6} \\ P_6 &=& \frac{5}{6} \times \frac{4}{5} \times \frac{3}{4} \times \frac{2}{3} \times \frac{1}{2} \times \frac{1}{1}= \frac{1}{6} \end{eqnarray*}

すなわち、通常のロシアンルーレットでは、1~6回目のどこで実弾に当たる確率も等しく1/6で、順番の後先に有利性はない。

毎回シリンダーを回転させる場合

1発だけ弾を込めた拳銃で、2人でロシアンルーレットで命をかける。ただし、それぞれが自分の番になる毎にシリンダーを回転させて、ランダムに止まったところで引き金を引く。自分が最初に打つのと、相手から打たせるのと、どちらを選ぶか。

 

毎回シリンダーを回転させるので、そこまで発砲されていなければ、実弾である確率は毎回1/6。n回目に実弾に当たる確率をp_nとすると、n-1回は当たらないことを考慮して、

(4)    \begin{equation*} p_n = \left( \frac{5}{6} \right) ^{n-1} \times \frac{1}{6} \end{equation*}

まず、この確率はnが大きくなるほどゼロに近づく。たとえば1回めで当たる確率は約16.7%、10回目で当たる確率は約3.2%、20回目で当たる確率は0.5%、40回目だと約0.01%程度となる。

次に、n回目までに当たる確率をP_nとすると、これは各回の確率を累積していくことで求められるので、等比数列の和より、

(5)    \begin{equation*} P_n = \sum_{i=1}^{n} \left( \frac{5}{6} \right) ^{n-1} \times \frac{1}{6} = \frac{1}{6} \frac{1-\left( \dfrac{5}{6} \right)^n}{1 - \dfrac{5}{6}} = 1-\left( \dfrac{5}{6} \right)^n \end{equation*}

この累積確率はn \rightarrow \inftyのとき1に近づくが、10回目で約83.8%、20回目で約97.4%、30回目で約99.6%、40回目で約99.9%となり、100回も打ってその時点で生き延びている確率はほとんどゼロに近い。

次に交互に打っていく場合を考える。

先攻で打つ方になった場合、1回目、3回目・・・と奇数階に打つことになるので、その累積確率をP_{1 \cdot n}とすると、

(6)    \begin{eqnarray*} P_{1\cdot 2n-1} &=& \sum_{k=1}^{n} \left( \frac{5}{6} \right)^{2(k-1)} \times \frac{1}{6} = \sum_{k=1}^{n} \frac{1}{6} \left( \frac{25}{36} \right)^{k-1} = \frac{1}{6} \cdot \frac{1 - \left( \dfrac{25}{36}\right) ^n }{1 - \dfrac{25}{36}} \\ &=& \frac{6}{11} \left( 1 - \left( \dfrac{25}{36}\right) ^n \right) \end{eqnarray*}

後攻で打つ方になった場合は、2回目、4回目・・・と偶数階に打つことになるので、その累積確率をP_{2 \cdot n}とすると、

(7)    \begin{eqnarray*} P_{2\cdot 2n} &=& \sum_{k=1}^{n} \left( \frac{5}{6} \right)^{2k-1} \times \frac{1}{6} = \sum_{k=1}^{n} \frac{5}{36} \left( \frac{25}{36} \right)^{k-1} = \frac{5}{36} \cdot \frac{1 - \left( \dfrac{25}{36}\right) ^n }{1 - \dfrac{25}{36}} \\ &=& \frac{5}{11} \left( 1 - \left( \dfrac{25}{36}\right) ^n \right) \end{eqnarray*}

同じnに対して常にP_{1 \cdot n} / P_{2 \cdot n} = 1.2となり、先に打つのを選んだほうが実弾に当たる確率は高く、この比率はn \rightarrow \inftyとしたときの結果と同じ。

したがって、「お先にどうぞ」と相手に最初を譲ったほうが、少しでも生き残る確率が高くなる。また、3人以上で順番に打っていく場合は、できるだけ後の順番で打つ方が実弾に当たる確率が低くなる。

条件付きの問題

2発の弾を並べて込める

ロシアンルーレットと少し違うが、条件付きの問題。

筋悪の金貸しから借りたかなりの借金を返せなくなり、命を取られようとしているが、「チャンスをやる」と言われた。彼は6発入りの拳銃の弾倉に2 発の弾を並べて込め、シリンダーを回す。シリンダーがランダムな位置で止まったところで、彼は言う。「今から空に向かって私が1回引き金を引く。その後にお前のこめかみに銃口を当てて打ってもらうが、そのまま打ってもいいし、もう一度シリンダーを回して止まった位置で打ってもいい」

 

1発目が空砲の場合

金貸しが銃を空に向けて引き金を引くと空砲だった。そのまま打つか、シリンダーを回転させるか、どちらを選択すべきか。

 

まず、シリンダーをもう一度回転させてから打つ場合は、6弾倉中2発残っているので、当たる確率は1/3。逆に助かる率は2/3となる。

一方シリンダーを回転させない場合は、手渡された拳銃の弾の状態を、円形に並んだ弾倉を一列で表し、下表のように整理する。ただし、左欄の●は実弾がある場所、○は実弾が入っていない場所で、1番目は金貸しが打ったときの位置、2番目は手渡された時の位置。右欄は2発目が実弾の場合は●、空砲の場合は○とする。

●●○○○○ 対象外
○●●○○○
○○●●○○
○○○●●○
○○○○●●
●○○○○● 対象外

金貸しが打ったときは空砲だったので、1番目が実弾の事象は対象外。このとき、実弾に当たらない確率は3/4となる。

すなわち、もう一度シリンダーを回転させるよりも、そのまま続けて打った方が助かる可能性が高い。

1発目が実弾の場合

もし、金貸しが最初に空へ向けて打ったときに実弾だった場合はどうか?

 

この場合に続けて打つと、1発目が実弾である2ケースに対して、空砲で助かる率は1/2。

シリンダーを回転させてから打つと、実弾は残り1発なので、当たらない確率は5/6で、回転させて打った方が生存確率は高くなる。

条件に応じた選択と確率

以上の結果を整理すると下表の通りとなり、1発目が空砲の場合と実弾の場合で、その後の選択による生存確率の高い方が逆転している。

空砲も実弾もその位置が連続しているため、1発目が空砲の場合は続けて空砲の確率が高く、1発目が実弾の場合は次も実弾の確率が高そうだが、1発目が実弾の場合は弾が1つ消費されるので、その影響で結果が逆転している。

1発目 選択 生存確率
空砲 シリンダー回転 1/3 (0.33)
空砲 続けて打つ 3/4 (0.75)
実弾 シリンダー回転 5/6 (0.83)
実弾 続けて打つ 1/2 (0.50)

実弾2発をランダムに込める

上記の金貸しの問題では実弾2発を並べて込めたが、これをランダムな位置に2発込めた場合はどうなるか。

この場合、2発の実弾の装填状況は下表のようになる。

1発目が→ 空砲 実弾
●●○○○○ 対象外  ●
●○●○○○ 対象外
○●●○○○ 対象外
●○○●○○ 対象外
○●○●○○ 対象外
○○●●○○ 対象外
●○○○●○ 対象外
○●○○●○ 対象外
○○●○●○ 対象外
○○○●●○ 対象外
●○○○○● 対象外
○●○○○● 対象外
○○●○○● 対象外
○○○●○● 対象外
○○○○●● 対象外

1発目が空砲だった場合

シリンダーを回転させた場合の生存確率は、4/6 = 2/3 (0.667)。

続けて打つ場合は、1発目が実弾のケースを除いて2発目が空砲の場合なので、6/10 = 3/5 (0.6)。

1発目が実弾だった場合

シリンダーを回転させた場合の生存確率は、5/6 (0.833)。

続けて打つ場合は、1発目が空砲のケースを除いて2発目が空砲の場合なので、4/5 (0.8)。

1発目が空砲でも実弾でも、シリンダーを回転させた方が生き残る確率が高くなる。

条件付確率~男女問題

概要

条件付き確率の代表的な問題として、2人の子の性別問題をよく見かけるが、前提条件によって答えが異なることを明確にしている例は少ない。

また、この問題がベン図を用いた分析や、ベイズの定理の親和性についても考えてみる。

兄妹の場合

まず準備として、以下の問題を考える。

2人兄弟の上の子が男であった場合、下の子が女である確率はいくらか。

 

普通に考えれば、男か女どちらかなのだから、確率は1/2と考えるが、まずは生真面目にすべての事象を並べてみる。

conditional-probability-brother-cases

上の子が兄か姉かに関係なく下の子が女である確率は1/2と直感的に考えられるが、それが確認できた。

一応、以下の様なベン図を考えてみる。図中、色付けしたところが条件下での事象で、濃い色が事後確率として求めたい部分。

conditional-probability-brother-venn-diagram

この場合、上の子が男(事象EM)のもとでの下の子が女(事象EMかつYF)ということになり、EMの要素が(男, 男)、(男, 女)の2つに対してEMかつYFの要素は(男,女)だけなので、確率は1/2となる。

なお、ベン図の代わりに場合分けの表で整理してみると、以下の様になる。
conditional-probability-brother-table

これを敢えてベイズの定理で書くと以下の様になるが、まあ当たり前という感じ。

(1)    \begin{equation*} P(YF|EM) = \frac{P(EM \cap YF)}{P(EM)} = \frac{1}{2} \end{equation*}

これをベイズの定理の別の表現で書くと以下の様になる。

(2)    \begin{equation*} P(YF|EM) = \frac{P(EM|YF)P(YF)}{P(EM)} = \frac{\dfrac{1}{2} \cdot \dfrac{1}{2}}{\dfrac{1}{2}}=\frac{1}{2} \end{equation*}

ただし P(EM|YF)=1/2としているが、この項の考え方は結局求めたい確率と同じ道筋で考えなければならない。

いずれにしてもこの問題は、第一子が男であろうが女であろうが、第二子が男か女かと問われれば、確率1/2でどちらか、という自然な結果となり、ベン図や場合分け表、ベイズの定理を使ったとしても、あまり恩恵は得られない。

区別なしの場合

次に以下の様な問題を考える。

2人の子のうち、1人が男の場合、もう1人が女である確率はいくらか。

 

これも普通に考えれば、男か女どちらかなのだから、確率は1/2と考えてしまいそうになるが、まじめに事象を考えてみる。

conditional-probability-2children-cases

この場合は1人が男とわかっているので、(姉, 妹)の事象は存在しなくなり、もう1人が女というだけで姉か妹かの区別はないことから、確率は2/3となる。

これをベン図で描いてみると以下のようになるが、男と女の組み合わせが2通りあることを確認する点では、上のような整理のほうがわかりやすい。

conditional-probability-2children-venn-diagram-1

場合分けの表は以下の通りになる。

conditional-probability-2children-table-1

これをベイズの定理で表現すると以下のようになる。

(3)    \begin{eqnarray*} P(F|M) &=& \frac{P(F \cap M)}{P(M)} = \frac{P(FM) + P(MF)}{P(MM) + P(MF) + P(FM)} \\ &=& \frac{\dfrac{1}{4} + \dfrac{1}{4}}{\dfrac{1}{4} + \dfrac{1}{4} + \dfrac{1}{4}} = \frac{2}{3} \end{eqnarray*}

条件付き確率から求める方法は、式(2)と同じ理由でメリットがない。

順番がある場合

次に以下の様な問題を考える。

2人の子がいる家庭を訪ねた。最初に挨拶に出てきたのが男の子だった場合、もう1人が女の子である確率はいくらか。

 

この場合は上の子と下の子を区別していないので、一つ前の問題と同じ答えになりそうだが、事象を列挙してみる。

conditional-probability-2children-by-order-cases

この問題でも、2人とも女のケースが除かれるが、兄弟構成に対して挨拶の順番がそれぞれ2通りずつあり、2人とも男の場合は兄、弟のいずれも最初に挨拶しうるので前提条件の事象に2つ含まれる。結果として、2人目が女の子である確率は1/2となる。

このように、2人兄弟の性別に関する問題でも、条件の付し方によって答えが異なってくるが、いずれの問題もベイズの定理を駆使するというものではなさそうである。

3人兄弟の場合

問題を以下の様に拡張する。

3人の子のうち2人が男の子の場合、残る1人が女の子である確率はいくらか。

 

これについても以下のように事象を列挙し、確率3/4を得る。

conditional-probability-3children-cases

 

ベイズの定理で表すと以下のようになるが、この場合もまじめに事象のパターンを列挙した考えるほうが素直。

(4)    \begin{eqnarray*} P(F|MM) &=& \frac{P(F \cap MM)}{P(MM)} \\ &=& \frac{P(MMF) + P(MFM) + P(FMM)}{P(MMM) + P(MMF) + P(MFM) + P(FMM)} \\ &=& \frac{\dfrac{1}{8} + \dfrac{1}{8} + \dfrac{1}{8}}{\dfrac{1}{8} + \dfrac{1}{8} + \dfrac{1}{8} + \dfrac{1}{8}} = \frac{3}{4} \end{eqnarray*}

 

ベイズの定理~難病検査

概要

ベイズの定理で典型例として説明される問題。ある病気の検査で陽性が出た場合に罹患している確率を求める。類似の問題として、鉱脈を探るのに試掘結果から鉱脈が存在する確率を求める問題がある。

ロジックとしては、「誤判定の可能性がある調査・検査の結果から、目的とする事実の確率を求める」という構図で共通している。

難病問題

病気の検査の問題を例示する。

ある難病の検査結果が陽性だったとき、その病気に罹患している確率を求めよ。ただし以下の情報が与えられている。

  • その難病は1000人に1人が罹患している
  • その難病にかかっている場合、90%の確率で検査結果は陽性になる
  • その難病にかかっていなくても、20%の確率で検査結果は陽性になる

 

ここで以下の記号を定義する。

  • 全体としての難病の罹患率→P(D)=0.001
  • 難病にかかっている場合に陽性になる確率→P(P|D)=0.9
  • 難病にかかっていない場合に陽性になる確率→P(P| \overline{D})=0.2

このとき、ベイズの定理により以下の確率を得る。

(1)    \begin{eqnarray*} P(D|P) &=& \frac{P(P|D) P(D)}{P(P|D) P(D) + P(P|\overline{D}) P(\overline{D})} \\ &=& \frac{0.9 \times 0.001}{0.8 \times 0.001 + 0.2 \times 0.999} \\ &\approx& 0.004484 \end{eqnarray*}

検査結果が陽性であっても、この難病にかかっている確率は0.5%未満ということになる。検査しなければ1000人に1人の罹患率なので0.1%なので、検査によってその確からしさが約4.5倍となるが、事前確率が小さい場合、検査の精度を上げても劇的な判定効果は望めない。

なお、この約4.5倍という値はP(P|D) / P(P|\overline{D}) = 4.5に相当し、事前確率P(D)の値が小さいほど4.5に近づく(ベイズの定理の解釈参照)。

 

ベイズの定理の解釈

ベイズの定理の変形

ベイズの定理は、一般に以下のように表現される。

(1)    \begin{equation*} P(T_k |C) = \frac{P(C|T_k)P(T_k)}{\displaystyle \sum_{i=1}^n P(C|T_i)P(T_i)} \end{equation*}

またはT\overline{T}の2事象の場合は、

(2)    \begin{equation*} P(T|C) = \frac{P(C|T)P(T)}{P(C|T)P(T) + P(C|\overline{T})P(\overline{T})} \end{equation*}

ここで次のように確率の記号を定義する。また、イメージを掴みやすくするために、難病検査の問題の場合を対比させる。

P_t = P(T)
ターゲットの事象が真である確率(true)あるいは事前確率。たとえば日本全体での難病の罹患率など。
P_c = P(T|C)
判定が真の条件下で事象が真である確率(under condition)あるいは事後確率。たとえば検査結果が陽性の場合に難病に罹患している確率。
P_h = P(C|T)
事象が真の場合に判定が真となる確率(hit)。たとえば難病に罹患している場合に検査結果が陽性となる確率。
P_f = P(C| \overline{T})
事象が偽なのに判定が正となる確率(fail)。たとえば難病に罹患していないのに検査結果が陽性となる確率。

P(\overline{T}) = 1 - P(T)であることに留意して、これらの記号でベイズの定理を表すと以下の通り。

(3)    \begin{equation*} P_c = \frac{P_h P_t}{P_h P_t + P_F (1 - P_t)} = \frac{1}{1 + \dfrac{P_f}{P_h} \left( \dfrac{1}{P_t} - 1 \right) } \end{equation*}

いくつかのケース

誤判定を絶対しない場合

(8)においてP_f = 0とおくと、P_t = 1となる。

難病の問題で言えば、「罹患していないときには必ず陰性判定となる(陽性とならない)」という検査に相当し、このような検査の結果が陽性判定なら必ず罹患していることになる。この時、罹患時に陽性となる確率P_hがいくらかは関係ない。

ただしこの逆は必ずしも保証されておらず、陰性判定でも罹患している場合がある。

完璧な検査

難病の問題で、上記に加えて「罹患しているときは必ず陽性判定となる(P_h = 1」という条件を加える。

まず、(2)をCの余事象について書くと以下の様になる。

(4)    \begin{eqnarray*} P(T|\overline{C}) &=& \frac{P(\overline{C}|T)P(T)}{P(\overline{C}|T)P(T) + P(\overline{C}|\overline{T})P(\overline{T})} \\ &=& \frac{(1 - P_h) P_t}{(1 - P_h) P_t + (1 - P_f)(1 - P_t)} \\ \end{eqnarray*}

ここで、P(\overline{T} | \overline{C}) = 1 - P(T| \overline{C})を考える。これは、陰性反応の時に難病にかかっていない確率に相当する。

(5)    \begin{eqnarray*} P(\overline{T} | \overline{C}) = 1 - P(T| \overline{C}) &=& 1 - \frac{(1 - P_h) P_t}{(1 - P_h) P_t + (1 - P_f)(1 - P_t)} \\ &=& \frac{(1 - P_f)(1 - P_t)}{(1 - P_h) P_t + (1 - P_f)(1 - P_t)} \end{eqnarray*}

(5)においてP_f = 0と置くと、

(6)    \begin{eqnarray*} P(\overline{T} | \overline{C}) = 1 - P(T| \overline{C}) = \frac{(1 - P_t)}{(1 - P_h) P_t + (1 - P_t)} \end{eqnarray*}

ここでP_h  = 1の場合はP(\overline{T} | \overline{C}) = 1となる。

この結果を難病の問題で言えば、検査結果が陰性の場合は必ず罹患していない、ということになる。

以上をまとめると、検査の性質が「罹患していなければ必ず陰性、罹患していれば必ず陽性となる」という場合、検査結果が陽性なら必ず罹患しており、陰性なら罹患していないという、至極当然の結果となる。

意味のない検査

(8)においてP_h = P_fと置くと、P_c = P_tとなる。

難病の例で言えば、罹患している時に陽性となる確率と、罹患していないときに陽性となる誤判定率が同じ場合、検査の意味がない(一般的な罹患率でしか罹患の程度がわからない)ということになる。

正しい判定の率が高くても、誤判定率が同じ場合は意味をなさない。

意味のある検査

(8)をP_f / P_hについて解く。

(7)    \begin{equation*} \frac{P_f}{P_h} = \frac{\dfrac{1}{P_c} - 1}{\dfrac{1}{P_t}- 1} \end{equation*}

この式で、P_f < P_hのとき、P_c > P_tとなり、検査が意味を持つことがわかる。

稀な事象

事前確率P_tがとても小さい場合を考える。たとえば難病の罹患率が1万人や10万人に1人といった場合。

P_t \approx 0とすると(8)は以下のように変形できる。

(8)    \begin{eqnarray*} P_c &=& \frac{1}{1 + \dfrac{P_f}{P_h} \left( \dfrac{1}{P_t} - 1 \right) } = \frac{P_t}{P_t + \dfrac{P_F}{P_h} (1 - P_t)} \\ &=& \frac{\dfrac{P_h}{P_F} P_t}{1 + \left( \dfrac{P_h}{P_f} - 1 \right) P_t} \approx \frac{P_h}{P_F} P_t} \end{eqnarray*}

すなわち、事前確率が十分に小さい場合は、検査の正誤判定確率の倍率分だけ事後確率が大きくなる。

たとえば難病検査の問題の場合、P_h = 0.9 , \; P_f = 0.2として、P_tが小さくなるほど、事後確率は正誤判定確率の倍率0.9/0.2 = 4.5倍に近づく。

(9)    \begin{eqnarray*} P_t = 0.1 & \rightarrow & P_c = \frac{0.9 \times 0.1}{0.9 \times 0.1 + 0.2 \times 0.9} \approx 0.333 \\ P_t = 0.01 & \rightarrow & P_c = \frac{0.9 \times 0.01}{0.9 \times 0.01 + 0.2 \times 0.99} \approx 0.0435 \\ P_t = 0.001 & \rightarrow & P_c = \frac{0.9 \times 0.001}{0.9 \times 0.01 + 0.2 \times 0.999} \approx 0.00448 \\ P_t = 0.0001 & \rightarrow & P_c = \frac{0.9 \times 0.0001}{0.9 \times 0.01 + 0.2 \times 0.9999} \approx 0.000449 \end{eqnarray*}

 

条件付き確率~ベイズの定理

基本

条件付き確率~ベイズの定理(Baye’s theorem)はとっつきにくいが、記号の使い方や図で理解することでわかりやすくなる。

事象Cが起こったときの事象Tの条件付き確率は、以下で計算される。

(1)    \begin{equation*} P(T|C) = \frac{P(T \cap C)}{P(C)} \end{equation*}

事象の記号ににABを使うのが一般的だが、私にはどちらが条件で、どちらを最終的に求めたいのかわかりにくいので、ここでT:Target、C:Conditionの記号を使った

P(C)は事前確率、P(T|C)は事後確率、P(T \cap C)は同時確率と呼ばれる。

ここでP(T \cap C) = P(T|C)P(C) = P(C|T)P(T)から、以下のようにも表現される。

(2)    \begin{equation*} P(T|C) = \frac{P(C|T)P(T)}{P(C)} \end{equation*}

一般表現

より一般的には、事象T_i (i=1,2,\ldots ,n)は互いに排反で、C \subset T_1 \cup T_2 \ldots \cup T_nとするとき、

(3)    \begin{equation*} P(T_k |C) = \frac{P(C|T_k)P(T_k)}{\displaystyle \sum_{i=1}^n P(C|T_i)P(T_i)} \end{equation*}

たとえばT_kが背反する2事象、すなわちT, \overline{T}の場合は以下のようになる。

(4)    \begin{equation*} P(T|C) = \frac{P(C|T)P(T)}{P(C|T)P(T) + P(C|\overline{T})P(\overline{T})} \end{equation*}

具体例として、癌などの難病の検査に関する問題が見られる。

また、ベイズの定理についてこちらでもう少し詳しい解釈をしている。