지폐와 동전의 분포

만약 반드시 지갑의 무게가 최소가 되도록 지불하고 있다면, 지갑의 내용은 어떤 분포가 될까요?

시뮬레이션

시뮬레이션으로 확인해 봅시다.

10,000엔은 무한한 것으로 합니다.

1만회, 상품을 사서 분포를 봅니다. (처음 100 번은 무시합니다.)

상품의 금액은, 100엔~9999엔으로 하고, 벤포드의 법칙에 따른 분포로 합니다.

난수 발생 (rand_from_prob)은 Walker's Alias ​​Method을 사용합니다.

지불 후 무게를 최소화하려면 조합 최적화 로 계산합니다.

파이썬으로 계산

우선, 벤포드의 법칙으로 100엔~9999엔의 무게(wgt)를 만들어 봅시다.

파이썬

import numpy as np, matplotlib.pyplot as plt
from math import log
# ベンフォードの法則
wgt = np.array([log((i+1)/i, 10000) for i in range(100, 10000)])
wgt /= sum(wgt)
plt.plot(wgt)
plt.xlabel('Price')

무게를 최소화한 후 개수를 반환하는 change를 정의합니다.

파이썬

from pulp import *
money_val = (1, 5, 10, 50, 100, 500, 1000, 5000)
money_wgt = (1.0, 3.7, 4.5, 4.0, 4.8, 7.0, 1.0, 1.0)
def change(price):
    m = LpProblem() # 数理モデル
    x = [LpVariable('x%d'%i, lowBound=0, cat=LpInteger)
         for i in range(len(money_val))] # 支払い後の個数
    m += lpDot(money_wgt, x) #目的関数(支払い後の重量)
    m += lpDot(money_val, x) == price # 支払い後の金額
    m.solve()
    return [int(value(i)) for i in x]

시뮬레이션 해 봅시다. 시험에 1000엔 지폐의 분포를 살펴보겠습니다.

파이썬

price = 0 # 現在の所持金
warm, nrun = 100, 10000
res = []
for i, p in enumerate(rand_from_prob(wgt, warm+nrun)):
    price -= p
    if price < 0:
        price += 10000
    if price:
        res.append(change(price))
a = np.array(res[-nrun:])
plt.hist(a[:,6], bins=5, range=(0, 5)) # 1000円札の分布

등 확률이군요. 다른 동전이나 5000엔 지폐도 마찬가지였습니다.

결론

등확률이 되는 것 같습니다. 총액의 분포도 0엔에서 9999엔의 등확률이 됩니다.

파이썬

import pandas as pd
from itertools import product
r2, r5 = range(2), range(5)
ptn = [np.dot(money_val, n) for nn in 
       product(r5, r2, r5, r2, r5, r2, r5, r2)]
plt.hist(ptn)
print(pd.DataFrame(ptn).describe())
>>>
                 0
count  10000.00000
mean    4999.50000
std     2886.89568
min        0.00000
25%     2499.75000
50%     4999.50000
75%     7499.25000
max     9999.00000

이상