近似を用いてサイコロの和を高速かつ省メモリ(O(1))に算出する
サイコロの出目の平均の分布が正規分布に近づくことからdice2のような近似が成り立つ。
できそうだからやったらここに書いていいのかわからん記事ができたtig.icon
code: dice.js
function dice1(num, max) {
const roll_result = new Array(num).fill(null).map(() => Math.floor(Math.random() * max) + 1);
const sum = roll_result.reduce((acc, cur) => acc + cur);
return sum;
}
function rnorm() {
return Math.sqrt(-2 * Math.log(1 - Math.random())) * Math.cos(2 * Math.PI * Math.random());
}
function calc_V(mean, max) {
return -((max + 1) * (max + 2) / 6 - mean * (max + 1) + mean * mean);
}
function dice2(num, max) {
const max_result = num * max;
if (!Number.isSafeInteger(max_result)) {
throw new TypeError("too large input!");
}
const mean = (max + 1) / 2;
const v = calc_V(mean, max);
const sigma = Math.sqrt(v / num);
while (true) {
const result = Math.round((sigma * rnorm() + mean) * num);
if (num <= result && result <= max_result) {
return result;
}
}
}
const m = new Map();
const m2 = new Map();
const r = new Map();
const num = 10000;
const max = 20;
const N = 100000;
for (let i = 0; i < N; ++i) {
const r1 = dice1(num, max);
m.set(r1, (m.get(r1) ?? 0) + 1);
const r2 = dice2(num, max);
m2.set(r2, (m2.get(r2) ?? 0) + 1);
}
}
if (r.has(k)) {
} else {
}
}
console.log(...r.map((k, v) => ${k},${v.join(",")}).join("\n")) 検証
https://gyazo.com/d6edd55b9e0ae2440831370358eb1d8e
https://gyazo.com/1b8bb28eb04b2a1e0cff1368d98b55e1
数学の話(といっても中学校程度の知識でわかると思う…tig.icon)
$ m面のサイコロについて考える。
中心極限定理より、サイコロの目の平均の分布はサイコロの個数$ nが大きいほど正規分布に近づく。 中心極限定理の収束の話が欲しい人はtigに言ってください(頑張って書くのでtig.icon つまり$ nが大きければ、正規分布に従う乱数を用いてサイコロの目の和を求めることができる。
でも、JavaScriptには一様分布な乱数を生成する関数しかない。
標準化の逆を行ってサイコロの分布の正規乱数を得る。
$ Zを標準正規分布、$ Xを正規分布$ N(\mu,\sigma^2)に従う確率変数として次式が成り立つ。
$ Z=\cfrac{X-\mu}{\sigma}
ところで、$ \sigma = \sqrt Vであり、$ x_iを$ m面のサイコロ1つの観測値として、次式のようになる。
$ mV=\sum_{i=1}^m (x_i-\mu)^2=$ \sum_{i=1}^m (i-\mu)^2 = $ \sum_{i=1}^m |i^2-2i\mu+\mu^2|= $ -(\frac{m(m+1)(m+2)}{6}-m(m+1)\mu +m\mu^2)
すなわち
$ V= -(\frac{(m+1)(m+2)}{6}-(m+1)\mu +\mu^2)
$ n個のサイコロの平均$ X'=\frac{1}{n}\sum_{i=1}^n X_iについて考えると$ X_iの分散について$ V_iとすると$ V_i = $ Vとなって
$ V'= \frac{1}{n^2} \sum_{i=1}^n V_i=\frac{nV}{n^2}=\frac{V}{n}
たまにありえない数値が出るのでその時はやり直す。
参考文献
具体例で学ぶ数学
高校数学の美しい物語
Wikipedia(Wikipediaを参考文献に書く違和感tig.icon)
Avlen AI Trend