2の補数

2019-07-28 / tau / コメントする

簡単なケース

正の数の表現

桁数が固定された2進数の加算を考える。たとえば4桁(4 bits)の場合に1ずつ加える。

$\begin{array}{cc} 0000 + 0001 = 0001 & (1)\\ 0001 + 0001 = 0010 & (2)\\ 0010 + 0001 = 0011 & (3)\\ 0011 + 0001 = 0100 & (4)\\ 0100 + 0001 = 0101 & (5)\\ 0101 + 0001 = 0110 & (6)\\ 0110 + 0001 = 0111 & (7) \end{array}$

負の数の表現

一方、-1は0から1を引いた値として計算される。最初の計算だけ、上位桁から1を借りてこられるとして、以下の様な計算になる。

$\begin{array}{cc} 0000 - 0001 = 1111 & (-1)\\ 1111 - 0001 = 1110 & (-2)\\ 1110 - 0001 = 1101 & (-3)\\ 1101 - 0001 = 1100 & (-4)\\ 1100 - 0001 = 1011 & (-5)\\ 1011 - 0001 = 1010 & (-6)\\ 1010 - 0001 = 1001 & (-7)\\ 1001 - 0001 = 1000 & (-8) \end{array}$

上の足し算の結果と下の引き算の結果をを見ると、以下のことがわかる。

正の数(0～7)と負の数(-8～-1)の合計15個で、4ビットの全てのパターンが網羅されている
正の数の最上位ビットは0、負の数の最上位ビットは1

引き算と補数の足し算

たとえば上の例で、正の数と負の数を加えてみる。

$\begin{array}{cl} 0101 + 1110 = 0011 & (5-2=3) \\ 0011 + 1001 = 1100 & (3-7=-4) \\ 1111 + 1100 = 1011 & (-1-4=-5) \end{array}$

2の補数を計算したときに0からその数を減じているので、当然の結果ではある。いずれにしても、負数を2の補数で表現することで、減算を加算で代えることができる。

2の補数を得る方法

2の補数を得るのに、いちいち0から引かなくても、以下の方法で可能。

整数のビットパターンを反転
1を加える

4ビットの例では以下のとおり。

$\begin{array}{cc} 0001 \rightarrow 1110 \rightarrow 1111 & (-1)\\ 0010 \rightarrow1101 \rightarrow 1110 & (-2)\\ 0011 \rightarrow1100 \rightarrow 1101 & (-3)\\ 0100 \rightarrow1011 \rightarrow 1100 & (-4)\\ 0101 \rightarrow1010 \rightarrow 1011 & (-5)\\ 0110 \rightarrow1001 \rightarrow 1010 & (-6)\\ 0111 \rightarrow1000 \rightarrow 1001 & (-7)\\ 1000 \rightarrow0111 \rightarrow 1000 & (-8)\\ \end{array}$

すなわち、固定長の整数の場合、ビット反転と加算機能があれば、減算を実現できる。

典型的なビット数の整数範囲

8ビット

byte型でよく見る値。

$\begin{array}{lllr} 0111\:1111 = &2^7 - 1 &=& 127 \\ 1000\:0000 = &-2^7 &=& -128 \end{array}$

16ビット

short型でよく見る値。

$\begin{array}{lllr} 0111\:1111\:1111\:1111 = &2^{15} - 1 &= &32767 \\ 1000\:0000\:0000\:0000 = &-2^{15} &= &-32768 \end{array}$

32ビット

一般的なint型で絶対値が約21億。

$\begin{array}{llr} 2^{31} - 1 &=& ‭2,147,483,647 \\ -2^{31} &=& -‭2,147,483,648‬ \end{array}$

64ビット

long型、絶対値が約920京（！）

$\begin{array}{llr} 2^{63} - 1 &=& ‭9,223,372,036,854,775,807 \\ -2^{63} &=& -‭9,223,372,036,854,775,808‬ \end{array}$

ユークリッドの互除法

2019-07-15 / tau / コメントする

概要

ユークリッドの互除法(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$ は $b$ と $r$ の公約数でもあることがわかる。

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

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

(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

def gcd(a, b):
	if a % b == 0:
		return b
	else:
		return gcd(b, a % b)

print( gcd(12, 8) )

def gcd(a, b):

if a % b == 0:

return b

else:

return gcd(b, a % b)

print( gcd(12, 8) )

CLisp

(defun mygcd (a b)
	(if (= (mod a b) 0) b (mygcd b (mod a b)))
)

(print (mygcd 18 12))

(defun mygcd (a b)

(if (= (mod a b) 0) b (mygcd b (mod a b)))

)

(print (mygcd 18 12))

最大公約数・最小公倍数

2019-07-13 / tau / コメントする

約数

約数の定義

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

整数 $m$ が $N$ の約数であるとき、 $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$ (整数に限らない)を整数倍した数である。

(4) $\begin{gather*}\cdots \; -3a,\; -2a,\; -a,\; 0,\; a,\; 2a,\; 3a,\; \cdots\end{gather*}$

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

最小公倍数

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

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

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

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

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

剰余と合同式

2019-07-10 / tau / コメントする

商と剰余

剰余(余り)について

$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, b$ は $d$ を法として合同である」という。

(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*}$

角度の例

以下の例では、330度と−30度が合同となっている。360度回転するたびに元の位置に戻るイメージ。

(11) $\begin{eqnarray*} 1050 &\equiv& 690 \bmod 360 \\ 690 &\equiv& 330 \bmod 360 \\ 330 &\equiv& -30 \bmod 360 \\ -30 &\equiv& -390 \bmod 360 \end{eqnarray*}$

合同式の性質

以下、合同式の $\mod 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*}$

【証明】

$\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$

合同式の積

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

【証明】

(14) $\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)$ のとき、以下が成り立つ。

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

【証明】

(16) $\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-c$ が $d$ の倍数となる。

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

合同式の冪乗

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

【証明】

(19) $\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*}$

(20) $\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*}$

二項定理

2019-07-10 / tau / コメントする

二項定理の表現

(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*}$

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

2019-07-04 / tau / コメントする

基本

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

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発目が空砲でも実弾でも、シリンダーを回転させた方が生き残る確率が高くなる。

条件付確率～男女問題

2019-07-01 / tau / 4件のコメント

概要

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

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

兄妹の場合

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

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

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

conditional-probability-brother-cases

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

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

conditional-probability-brother-venn-diagram

ここで記号E/Yはelder/younger、M/Fはmail/femailを表す。この場合、上の子が男（事象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*}$

ベイズの定理～難病検査

2019-07-01 / tau / コメントする

概要

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

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

難病問題

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

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

その難病は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に近づく(ベイズの定理の解釈参照)。

なお、2020年、世界的に大きな影響を及ぼしたCOVID-19（新型コロナウイルス）のPCR検査を題材にした記事をこちらにまとめている。

ベイズの定理の解釈

2019-07-01 / tau / コメントする

ベイズの定理の変形

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

(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*}$