財布内の最小小銭枚数の期待値（日本円）

財布の小銭最少化問題の極北〜694円の会計に1245円出す人〜 - Togetterまとめのブコメで、「小銭最適すると、小銭枚数の収束値がありそうな気がするけど、誰かモンテカルロ法かなんかで確かめてよ。 - chess-news のコメント / はてなブックマーク」というのがあって、計算で求まるんじゃね？と思ったのでそれについてざっくり書き記す。

あってるかよくわからない + もっと簡単に求まりそう。

問題

無限に支払をし続けた場合、財布内小銭枚数の期待値の収束値を求めよ。ただし、下記7つを仮定する。

1. 財布内には額面が1000のお札が無限にある
2. 財布内の小銭は有限枚数しかなく、初期では各小銭の枚数は無作為な非負整数値をとる。
3. 支払と釣り銭に使用できる小銭の額面は[1,5,10,50,100,500]のみである
4. 釣り銭は常に最小の小銭枚数で返され、そのために[1,5,10,50,100,500]の各額面の小銭と額面が1000にお札が無制限に使用できる
5. 支払は支払い後の財布内の小銭の枚数が最小になるようにしなければならない
6. 条件5を満たす限りにおいて、支払に使用する小銭の枚数を最小とする
7. 購入価格は無作為な非負整数値ををとる（価格０ = 両替もあり得る）

財布内の小銭を全て使用する支払い方

条件6に反する可能性があるが、財布内の小銭を全て使用する支払い方をすると、条件4より支払い後の財布内の小銭枚数は必ず最小化される。条件6は条件5を満たす必要があるため、「財布内の小銭を全て使用する支払い方」より悪い（支払い後の財布内の小銭枚数が増える）支払い方をできない。そのため、支払い後の財布内小銭枚数は、「財布内の小銭を全て使用する支払い方」と一致する。

構成の存在

次のように、小銭と1000円札である非負整数の金額 $T$ を表すことを考える。なお、$N_k$ は$k$円玉（札）の枚数を表す。

$T = 1000 N_{1000} + 500 N_{500} + 100 N_{100} + 50 N_{50} + 10 N_{10} + 5 N_{5} + N_{1}$

$T$を構成する$[N_1,N_5,\dots,N_{1000}]$の組は必ず存在する、なぜなら少なくとも$N_{1} = T$の構成が存在するためである。

最小枚数の構成の一意性

$T$を表す貨幣の枚数 $N$ は次式で表せる。

$N = N_{1000} + N_{500} + N_{100} + N_{50} + N_{10} + N_{5} + N_{1}$

$k \times N_{k} = l$ ならば、$k$ 円貨幣 $N_k$ 枚で表現するより、$l$ 円貨幣 1 枚で表現するほうが$N$は小さくなる。例えば、1000円を表すならば、500円玉２枚で表すより、1000円札１枚で表す方が$N$の値は小さくなる。そして、日本円（額面が[1,5,10,50,100,500,1000]の貨幣）は、小さい貨幣が大きい貨幣の約数となっている。

そのため、$N$を最小にするとき次の条件が成り立つ。ただし、$j_0, j_1, j_2, j_3, j_4, j_5, j_6 = 1,5,10,50,100,500,1000$である。

\begin{align}
N_{1000} &= \lfloor T/1000 \rfloor \\
T_{1000} &= T - 1000 \times N_{1000} \\
N_{j_i}  &= \lfloor T_{j_{i+1}}/j_{i} \rfloor \\
T_{j_i} &= T_{j_i+1} - j_{i+1} \times N_{j_{i+1}} \tag{1}
\end{align}

あとは、剰余定理から$N$を最小にするとき$T$を構成する各貨幣の枚数が一意に定まるとわかる。

各小銭枚数の取りうる範囲

式(1)よりどのような$T$についても、$N$を最小化するとき次の条件が成り立つ。

\begin{align}
0 \le N_{500} \lt 2 \\
0 \le N_{100} \lt 5 \\
0 \le N_{50} \lt 2 \\
0 \le N_{10} \lt 5 \\
0 \le N_{5} \lt 2 \\
0 \le N_{1} \lt 5 \tag{2}
\end{align}

財布内小銭金額合計の取りうる確率

以上より、次のことがわかる。

• $n$ 回目の支払後の財布内小銭金額合計を $C_n$ とする
• $n$ 回目の購入価格の財布内小銭金額合計を $T_n$ とする
• $n > 0$ ならば $0 \le C_n \le 999$
• $C_n$ を最小の枚数で成す小銭の構成 $[N_1,N_5,\dots,N_{500}]$ は一意に存在する
• $n > 1$ ならば $T_n$ について、$1000 \times \lfloor T_n/1000 \rfloor$ 円分については必ず1000円札で支払われる

ここで、$T_n^{\prime} = T_n - 1000 \times \lfloor T_n/1000 \rfloor = T \bmod 1000$とすると、$T_n^{\prime}$は 0 から 999 の間の整数値を一様な確率で取る。また、$n > 0$のとき、次式が成り立つ。

C_{n+1} = \begin{cases}
 C_n - T_{n+1}^{\prime}  & (C_n \ge T_{n+1}^{\prime}) \\
 1000 + C_n - T_{n+1}^{\prime} & (C_n \lt T_{n+1}^{\prime})
\end{cases}

これより、恐らく、$C_n$ は $n > 1$ のとき、 0 から 999 の間の整数値を一様な確率で取る。（数学的帰納法使わないと $C_n$ の分布は求まらないだろうし、そのためには $C_1$ の確率をちゃんと求めないといけない）

したがって、問題の答えは 0 から 999 の各値を構成する小銭の最小枚数の平均値が答えとなる。

答え

7.5

Try Jupyter! で下記コードを実行して求めた。

def coins(n):
    js = [1000,500,100,50,10,5,1]
    return [(n % k) // l for (k, l) in zip(js[:-1], js[1:])]

xs = [sum(coins(n)) for n in range(1000)]

print ("Answer = ", sum(xs)/len(xs))

分布

from matplotlib import pyplot as plt
%matplotlib inline 

plt.hist(xs, bins=16, range=(-0.5, 15.5), normed=True)

plt.xlim([-0.5,15.5])

plt.title("Histgram")
plt.xlabel("number of coins")
plt.ylabel("frequency")

plt.show()