読者です 読者をやめる 読者になる 読者になる

唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

拡張ユークリッドの互除法

\(a, b\)の2つの正の整数が与えられたときに\(ax+by=\gcd(a, b)\)となるような整数\(x, y\)のうちの1つの組を計算するアルゴリズム
たとえば5リットルの入れ物と7リットルの入れ物を使って11リットルの水を汲む方法などが計算できる

昔こんなツイートをしてたようですがようやく理解できた気がします(遅すぎ。中国の剰余定理の方はまだ)

Wikipediaの説明を読んだらよくわからなくて???となったがいろいろググってなんとか理解した
\(a, b\)の2つの整数についてユークリッドの互除法をやるときに、\(ax_1+by_1=a\)と\(ax_2+by_2=b\)みたいに両辺がある形で考えて\(a(x_1 - 3x_2)+b(y_1-3y_2)=a - 3b\)みたいに両辺とも引き算していきながらユークリッドの互除法をやればよいらしい

ユークリッドの互除法

\(a, b\)の2つの整数の最大公約数を求める方法

  1. コード上は必要ないが説明しやすくするため\(m = a, n = b\)と代入しておく
  2. \(m\)を\(n\)で割った余りを計算する。余りが\(0\)なら\(n\)が\(a, b\)の最大公約数
  3. 余りが\(0\)でないなら\(m\)に\(m\)を\(n\)で割った余りを代入する。\(m\)と\(n\)を入れ替えて2.の処理に戻る
def euclid(a, b):
    assert a > 0
    assert b > 0
    
    m, n = a, b
    while m % n != 0:
        q = m / n
        m, n = n, m - q * n
    
    return b

拡張ユークリッドの互除法

  1. \(ax_1+by_1=m\)と\(ax_2+by_2=n\)の形の式2つを使って計算していく。ただし最初は\((x_1, y_1, m)=(1, 0, a), (x_2, y_2, n)=(0, 1, b)\)とする
  2. \(m\)を\(n\)で割った余りを計算する。余りが\(0\)なら\(n\)が\(a, b\)の最大公約数で\((x_2, y_2)\)が\(ax_2+by_2=\gcd(a,b)=n\)を満たす整数
  3. 余りが\(0\)でないなら通常のユークリッドの互除法で\(m\)を\(n\)で割った余りを代入したのと同様の計算を両辺についてする。つまり\(m\)を\(n\)で割ったときの商が\(q\)なら\(ax_1+by_1- q(ax_2+by_2)=m-qn\)、整理すると\(a(x_1-qx_2)+b(y_1-qy_2)=ax'_1+by'_1=m-qn =m'\)となる。通常のユークリッドの互除法と同様に\((x'_1, y'_1, m')\)と\((x_2, y_2, n)\)の変数を入れ替えて2.の処理に戻る
def extended_euclid(a, b):
    assert a > 0
    assert b > 0
    
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q = m / n
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, m - q * n
    
    return (x2, y2, n)

ベズーの等式

\(a, b\)が\(0\)でない整数の時\(ax+by=\gcd(a, b)\)となる\(x, y\)が存在するらしい
また\(ax+by=c\)が整数となるような\(c\)は\(\gcd(a, b)\)の倍数に限られる
拡張ユークリッドの互除法で得られる\(x,y\)の組は解の一つであり、すべての組は\((x+k\frac{b}{\gcd(a,b)}, y+k\frac{a}{\gcd(a,b)})\)で表される(ただし\(k\)は任意の整数)

合同式(modの計算)の逆元

また拡張ユークリッドの互除法を使って\(a, b\)が素数(または互いに素)であるときに\(ax \equiv 1 \pmod {b}\)となるような\(x\)を計算することができます。このような\(x\)は\(a\)で割り算をしたいときに代わりに使えるのでとても重要です
拡張ユークリッドの互除法によって\(ax+by=1\)となるような\(x, y\)が求められます
\(ax+by=1\)の両辺を\(\pmod {b}\)であると考えると\(ax \equiv 1 \pmod {b}\)となるので、拡張ユークリッドの互除法で求められた\(x\)が求めたい値になります(ちなみに負の数になった場合は\(b+x\)を使えばよさそう)

グループ別の解約率の逆数で計算したユーザーの平均継続期間が全体の解約率で計算した数値と合わない?

解約率が一定であると仮定すると、解約率の逆数でユーザーの平均継続期間を求めることができます
以下の記事がバズっていた後に、解約率からユーザーの平均継続期間を計算するのを試しているのを見かけました
ところが全体の解約率で計算した値と、ユーザーを属性別に分けて出した解約率を元に計算した値に結構差があって不思議そうな様子でした
migi.hatenablog.com

どんな感じになるのか例を出してみます

ユーザーが\(10\)人いて、月間の解約率が\(p=\frac{3}{4}\)であるとします
これらのユーザーの平均継続期間は解約率の逆数でそれぞれ\(E=\frac{1}{p}=\frac{4}{3}\)ヶ月になります。継続期間を人数倍すると\(\frac{40}{3}\)ヶ月です

実はこの\(10\)人のユーザーは解約率が\(p_A=\frac{1}{2}\)のユーザーが\(5\)人(グループA)、解約率が\(p_B=1\)のユーザーが\(5\)人(グループB)だったと考えます。この場合でも全体の平均解約率は元と同じ\(p=\frac{5 \times p_A + 5 \times p_B}{10}=\frac{3}{4}\)です
グループAの平均継続期間は\(E_A=\frac{1}{p_A}=2\)ヶ月になります。継続期間を人数倍すると\(10\)ヶ月です
グループBの平均継続期間は\(1\)ヶ月になります。継続期間を人数倍すると\(5\)ヶ月です

グループAとBの継続期間の人数倍を合計すると\(15\)ヶ月になります
それに対して全体の継続期間の人数倍は\(\frac{40}{3}\)ヶ月になってしまい、グループAとBの合計よりも少なくなってしまいました

合計が合わなくなる理由

平均継続期間の計算では解約率が一定であることを仮定しています
つまり全体で計算するときには全体の解約率が一定として計算しています
ところがグループそれぞれで平均継続期間を計算するときにはそれぞれのグループについて解約率が一定として計算することになります
それぞれのグループの解約率が一定とすると、解約率の高いグループの人数は低いグループに比べて速く減っていくので、複数のグループを混ぜたときには全体の解約率はどんどん下がっていき、全体の解約率が一定という仮定が成り立たなくます
つまり全体の解約率が一定ではなくなるので、全体の解約率の逆数による平均継続期間の計算とは合わなくなります

また数式的にみると、グループA、Bの期待値がそれぞれ\(E_A=\frac{1}{p_A}\)、\(E_B=\frac{1}{p_B}\)なのに対して全体の解約率で出した平均継続期間は以下のようになります
$$E=\frac{1}{p}=\frac{10}{5 \times p_A + 5 \times p_B}=\frac{10}{5 \times \frac{1}{E_A} + 5 \times \frac{1}{E_B}}=\frac{2E_A E_B}{E_A + E_B}$$
\(E\)は\(E_A, E_B\)を定数倍したものを足し合わせても表現できないことは明らかです

ちなみに\(E=\frac{10}{5 \times \frac{1}{E_A} + 5 \times \frac{1}{E_B}}\)の式は調和平均の形$$\frac{n}{\sum^n_i \frac{1}{x_i}}$$になっています

調和平均は、平均されるそれぞれの値が等しくないときには相加平均\(\frac{E_A+E_B}{2}\)より小さな値になることが知られているので、このことからも全体の平均継続期間がそれぞれのグループで計算した値よりも小さくなることが言えます

まとめ

全体で解約率を求めて平均継続期間を求めたものの人数倍と、グループ別に分けて解約率を求めて平均継続期間を求めたものの人数倍の合計は合わない

おまけ

元の記事では解約率が\(p\)のときに平均継続期間(継続期間の期待値)が\(\frac{1}{p}\)になるのを幾何級数を使って証明していましたが、最初の1回目の試行について考えて期待値の方程式を書くと簡単に解けます
期待値は解約しないときすなわち確率が\(1 - p\)のとき\(1\)増えて\(E + 1\)となります
解約するときにはすなわち確率\(p\)でやめたので期待値は\(1\)です
これを式にすると以下のようになります
$$E=(1 - p)(E + 1)+p \times 1$$
方程式を解くと、期待値は解約率の逆数になります
$$E = \frac{1}{p}$$

-->