Graviness Blog

算数・数学・科学・電脳・雑記・アホの順の密度で記事が構成されます.
<< July 2017 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 >> ブログランキング・にほんブログ村へ
 
RECOMMEND
ビッグバン宇宙論 (上)
ビッグバン宇宙論 (上) (JUGEMレビュー »)
サイモン・シン, 青木 薫
RECENT COMMENT
  • 豊臣秀吉と曾呂利新左衛門から学ぶ数列の和
    優乃 (07/12)
  • 【誰か解いて】漸化式 a_(n+1) = f(n) * a_n ^ g(n) + h(n) の一般項
    優乃 (02/18)
  • 【誰か解いて】漸化式 a_(n+1) = f(n) * a_n ^ g(n) + h(n) の一般項
    S.S.+ (02/16)
  • 豊臣秀吉と曾呂利新左衛門から学ぶ数列の和
    坂井昭 (03/19)
  • d/dx(x↑↑n): 高さが定数のテトレーションの微分 - 数学的帰納法を用いる方法
    (09/30)
  • 全ての三角形は二等辺三角形
    優乃 (09/28)
  • 全ての三角形は二等辺三角形
    亀レス (09/28)
  • 全ての三角形は二等辺三角形
    優乃 (09/24)
  • 全ての三角形は二等辺三角形
    亀レス (09/23)
  • 【未解決】新しい演算子を創る
    $_ (09/10)
RECENT TRACKBACK
MOBILE
qrcode
PROFILE
無料ブログ作成サービス JUGEM
 
全種類のおもちゃを手に入れるまでのガチャガチャの平均回数をできるだけ早く計算する
前回記事の続きです.タイトルはそうなってますが,たまたま目的の値と同じだから書いてるだけで,別にガチャガチャしたいわけではないですイヒヒ

さて,前回記事に示す通り,N種類のおもちゃを手に入れるまでのガチャガチャの平均回数は以下の式で表されます.

  (平均回数) = N * Σ[k = 1, N](1 / k) = N * (1 + 1/2 + 1/3 + 1/4 + … + 1/(N - 1) + 1/N)

計算は単純ですが,私が知りたいのは,例えば,Nが一万個のときのガチャガチャの平均回数です.この式では一万回の足し算をしなくちゃいけませんので,日が暮れます(いや,実際は暮れませんグッド).ということでこの記事では,別の方法を考えます.
さて,ここで,以下の公式が登場します.Σ[k = 1, N](1 / k) は,調和級数と呼ばれています.どうでもいいですが,“調和”の由来は音です.昔の数学者さんは,調和音が,逆数に関連するものと知っていたのです星

  オイラーの定数 γ := lim[N→∞] (Σ[k = 1, N](1 / k) - ln(N))

  

この公式の意味は,「調和級数と自然対数極限における差が定数である」です.オイラーの定数 γ の値は,約0.57721 56649 01532 86060 65120 90082 40243 ... となります.

上式の両辺にNを掛けます.

  N * γ = N * Σ[k = 1, N](1 / k) - N * ln(N) (N → ∞)

  

よって

  N * Σ[k = 1, N](1 / k) = N * ln(N) + N * γ (N → ∞)

この左辺,“平均回数”そのものです.これで,しゅうりょ〜!拍手と行きたいところですが,N → ∞ においてのみ成り立つ式ですので,どう足掻いても,宇宙開闢時代からでも(意味不明),近似式レベルでしか使用できません.実用に耐えうるか検証が必要です.ということでグラフにしてみました.横軸がN,縦軸が δ = N * Σ[k = 1, N](1 / k) - (N * ln(N) + N * γ) の値です.つまり,Nの値によって,上式の左辺と右辺にどの程度の誤差があるかを示したものです.

  

N=1から1000で,誤差の最小値が約0.42,最大値が約0.5です.その間の実値は,1から7000とかですので大丈夫そうですね.
※とか実は,幾分誤魔化してますふぅ〜ん・・・Nが大きくなるにつれて,δは徐々に0に近づくはずですが,この0.5に漸近しているように見えるのは何でしょうか?計算誤差によるものでもなさそうです.調和級数や対数関数の性質(増加が極端に遅い)を引きずってる?分かる方教えて下さい.当該グラフを作成したエクセルファイルはこちらです.

よって,N種類のおもちゃを手に入れるまでのガチャガチャの平均回数は,以下の式で求められる.
  (平均回数) ≒ N * (ln(N) + γ)
    ln : 自然対数
    γ:オイラーの定数


【2009/02/22: 記事の内容を修正】
上記で引用した公式の使用方法が誤っており,内容が正確でなかったので,以下に修正した記事を追記しました.アトムさん,ありがとうございました.ところで,オイラー・マクローリンの公式でググッたらアトムの物理ノートがトップに表示されたのにびっくりです.

上記の約0.5の誤差は,公式の使用方法が間違っているためだと分かりました.オイラーの定数の式と異なるのは,Nを掛けているか,そうでないかの違いで,Nを掛けるとき,無視できていた値が“活きて来る”ものがあったようです.ということで基本の式に立ち返り,以下のオイラーマクローリンの式 (アトムの物理ノートVer.)を使用します.

  ∫[0, n] f(x) dx = (1 / 2) * f(0) + f(1) + f(2) + ... + f(n - 1) + (1 / 2) * f(n)
    + Σ[k=2, p]{(-1)k-1 / k! * Bk * (f(k - 1)(n) - f(k - 1)(0))}
    + Σ[a=0, n-1]{(-1)p / p! * ∫[0, 1] Bp(x) * f(p)(x + a) dx}
    Bk(x) : ベルヌーイ多項式
    Bk : ベルヌーイ数


上式を少し書き直します.

  Σ[i = 1, n] f(n) = ∫[0, n] f(x) dx + (1 / 2) * (f(n) - f(0))
     - Σ[k=2, p]{(-1)k-1 / k! * Bk * (f(k - 1)(n) - f(k - 1)(0))}
     - Σ[a=0, n-1]{(-1)p / p! * ∫[0, 1] Bp(x) * f(p)(x + a) dx}


上式より

  Σ[i = n+1, m] f(i) = Σ[i = 1, m] f(i) - Σ[i = 1, n] f(i)
     = ∫[0, m] f(x) dx + (1 / 2) * (f(m) - f(0))
      - Σ[k=2, p]{(-1)k-1 / k! * Bk * (f(k - 1)(m) - f(k - 1)(0))}
      - Σ[a=0, m-1]{(-1)p / p! * ∫[0, 1] Bp(x) * f(p)(x + a) dx}
      - ∫[0, n] f(x) dx - (1 / 2) * (f(n) - f(0))
      + Σ[k=2, p]{(-1)k-1 / k! * Bk * (f(k - 1)(n) - f(k - 1)(0))}
      + Σ[a=0, n-1]{(-1)p / p! * ∫[0, 1] Bp(x) * f(p)(x + a) dx}


同類項でまとめて整理すると

  Σ[i = 1, m] f(i) - Σ[i = 1, n] f(i)
    = ∫[n, m] f(x) dx + (1 / 2) * (f(m) - f(n))
     - Σ[k=2, p]{(-1)k-1 / k! * Bk * (f(k - 1)(m) - f(k - 1)(n))}
     - Σ[a=n, m-1]{(-1)p / p! * ∫[0, 1] Bp(x) * f(p)(x + a) dx}


ここで,f(x) = 1 / x とすると,f(k)(x) = (-1)k * k! / xk + 1 であるので,代入して整理すると

  Σ[i = 1, m] (1 / i) - Σ[i = 1, n] (1 / i)
    = log(m) - log(n) + (1 / 2) * (1 / m - 1 / n)
     - Σ[k=2, p]{(Bk / k) * (1 / mk - 1 / nk)}
     - Σ[a=n, m-1]{∫[0, 1] Bp(x) / (x + a)p + 1 dx}


γk = Σ[i = 1, k](1 / i) - log(k) とおけば,

  γm = γn + (1 / 2) * (1 / m - 1 / n)
     - Σ[k=2, p]{(Bk / k) * (1 / mk - 1 / nk)}
     - Σ[a=n, m-1]{∫[0, 1] Bp(x) / (x + a)p + 1 dx}


m → ∞ の極限をとり,Rp = limm → ∞(-Σ[a=n, m-1]{∫[0, 1] Bp(x) / (x + a)p + 1 dx}) とおくと

  γ = Σ[i = 1, n](1 / i) - log(n) - 1 / (2 * n) + Σ[k=2, p]{(Bk / k) / nk} + Rp
  ∵ γ := Σ[i = 1, k](1 / i) - log(k) (k → ∞)


ここで,p = 2 とすれば,

  γ = Σ[i = 1, n](1 / i) - log(n) - 1 / (2 * n) + 1 / (12 * n2) + R2
  ∵ B2 = 1 / 6


両辺に n を掛けて,移項すると

  n * Σ[i = 1, n](1 / i) = n * log(n) + n * γ + 1 / 2 - 1 / (12 * n) - n * R2

左辺は目的の式そのものである.さて,R2 は以下であった.

  R2 = -Σ[a=n, m-1]{∫[0, 1] B2(x) / (x + a)3 dx} (m → ∞)

※この値は誤差を示すので,ここからゴニョゴニョ展開して,R2 ≦ ??? と示したいが,私の知識では,限界!なので,アトムさんの 残されたRpは大抵の場合急激に小さくなりますから をそのまま引用する ^^;

よって,N種類のおもちゃを手に入れるまでのガチャガチャの平均回数は,以下の式で求められる.

(平均回数) ≒ N * (ln(N) + γ) + 1 / 2 - 1 / (12 * N)
ln : 自然対数
γ:オイラーの定数

実際の値を求めてみます.

  ・おもちゃが10種類のとき
  (平均回数) ≒ 10 * (ln(10) + 0.57721) + 1 / 2 - 1 / 120 ≒ 29
  ・おもちゃが100種類のとき
  (平均回数) ≒ 100 * (ln(100) + 0.57721) + 1 / 2 - 1 / 1200 ≒ 519

幼少時代にこの公式を知ってたら,ガチャガチャに無駄に金を投資しなかった,かは定かではない.今なら,面倒くさいので,ガチャガチャごと買うだろう(大人買いwww
コメント
from: アトム   2009/02/22 9:22 AM
頭が働かないので、ランダムふって、N=10の場合は大体29回っぽいとでました。(統計わすれたので、偏差などはとってません)。

でN→∞の場合ですが

Σ_{k=1,N} 1/k 〜log(N)+γ+1/(2N)+O(1/N^2)

を使わなくてはなりません。評価したいのはNをかけた式なので通常は無視する1/(2N)の項まで考慮するべし。

さすがに数値計算で誤差が0.5あるというのは的中です(笑)。統計誤差ではなかったようです。楽しめました。
from: 優乃   2009/02/26 7:50 PM
返信遅れました.この1週間ほど,特定のWebサイトにつながらない事態に陥っておりました.

特定のWebサイト1≒このブログ (ふざけんなぁーーーーー)

特定のWebサイト2=アトムさんの記事に書き込みするときのスパム対策用の認証画像

アドバイスありがとうございます!すっきりしたとともに記事も全面的に修正しました.
コメントする









 
トラックバック
この記事のトラックバックURL
http://blog.graviness.com/trackback/810041
 

(C) 2017 ブログ JUGEM Some Rights Reserved.