『出揃うまでの回数』

『出揃うまでの回数』解答

◆愛知県　迷子の雄猫さんからの解答。

【問題１】

１つ目は一回目で必ずでる。

２つ目は５
６の確率ででるから、
確率的には６回振れば５個出ることになる。

よって、１個出るための平均の回数は６
５回

同様に、３つ目は６
４＝３
２回、

４つ目は６
３＝２回、

５つ目は６
２＝３回、

６つ目は６
１＝６回

答

１つ目＝１＝１

２つ目＝１＋６
５＝２＋１
５

３つ目＝１＋６
５＋３
２＝３＋７
１０

４つ目＝１＋６
５＋３
２＋２＝５＋７
１０

５つ目＝１＋６
５＋３
２＋２＋３＝８＋７
１０

６つ目＝１＋６
５＋３
２＋２＋３＋６＝１４＋７
１０

【問題２】

ｋ＝１の場合には
R
Σ
s=1 _nＣ₁
_n-sＣ₁

までは判りますが・・・
ここから手がつけられないです（汗）

◆兵庫県　sinapusu さんからの解答。

VBAコードです。
数式的に解こうと思ったのですが、お手上げになったのでとりあえず作成しました。

n=ダイスの面数
datums=全部の目が出る確率がこれ以上になって欲しい確率

全部の目がdatums以上になる回数を求めるコードです。

datums=0.3としたら何回か振ったときに全部の目が出る確率が30％以上になっていたらその回数を書き出して終了します。

桁落ちや数値計算に関する知識がないものでｎを大きくするとすさまじい誤差が出ているかもしれません。

ポコペンさんのおかげでこのコードが作成できました。

Sub allDice()
Dim n, datums, i
’ここのデータを弄ってください
n = 16
datums = 0.5

Dim m
m = n - 1

Dim a() As Double
ReDim a(m)
a(0) = 1

'無限ループ防止のためにとりあえずｎ*10回目までサイコロ振る
For i = 1 To n * 10
    a = sigumaNext1(a)
    If datums < a(m) Then
        Debug.Print i + 2 & "回目で越えました"
        Exit Sub
    End If
Next
End Sub
Function sigumaNext1(ByRef a() As Double) As Double()
Dim b() As Double
Dim last
Dim count, i
last = UBound(a)
ReDim b(last)
count = last + 1
b(0) = a(0) * 1 / count
For i = 1 To last - 1
    If a(i - 1) > 0 Then
        b(i) = a(i - 1) * (count - i) / count
    End If
    If a(i) > 0 Then
        b(i) = b(i) + a(i) * (i + 1) / count
    End If
Next
    b(last) = a(last) + a(last - 1) * 1 / count
    sigumaNext1 = b
End Function

◆愛知県　Y.M.Ojisan さんからの解答。

【問題２】

数式ではなく、有限回での計算方法を示します。

　一般にある多成分の確率状態Ｓ(k)が
確率行列Ｂにより　Ｓ（k+1)=B*Ｓ(k)　で遷移し、
Ｂの固有値の絶対値が１未満なら、

期待値 ∞
Σ
I=1 Ｉ*B^I-1S(1) は(Ｂ－Ｅ)^-2S(1)　に収束する。

なお、ここでＥは単位行列である。

「Ｒ種類以上が出揃う」を考える場合、Ｓの次元はＲで良い。
また、S(1)はＫ（＝選ぶ数）番目のみ１で他は０である。

　ＢのI行Ｊ列の成分は　Ｋ≦J＜R　Ｊ≦Ｉ≦min(Ｊ＋Ｋ,R-1)　において　
Ｎ－ＪＣＤ×ＪＣＫ-Ｄ/ＮＣＫである。
ここでＤは新規増加分　D=I-Jである。

　Ｋ≦J＜R　Ｉ＝R においては　各列の成分の和を１とする値である。
また、J=R列はそこで終了なので確率０とする。
このようにして得られたＢは下三角行列であり、固有値は対角成分である。
従って固有値は非負で１未満である。

Ｎ＝６　Ｋ＝１　Ｒ＝４の場合のＢの例を示す。

　最終的に得たい期待値はＲ番目の成分であり、S(1)はＫ番目だけが１なので、
結局　（Ｂ－1）^-2のＲ行Ｋ列成分が答えである。

　BASICのソースを下記に示します。
１～Ｋ－１の成分は常に０であり、計算するのは無駄なので、Ｋ～Ｒ成分の部分のみ計算している。

なお、十進BASIC（http://www.vector.co.jp/authors/VA008683）（有理数、グラフィクス上書きモード）使用前提です。

!!!    出揃うまでの回数の期待値   !!!  CopyRighted by YMOjisan
!!!    十進BASICのホームページ  http://www.vector.co.jp/authors/VA008683/

! ----- 設定条件 --------
LET  選択枝数=6
INPUT 選択数
LET  N=選択枝数
LET  K=選択数

! ----- 宣言 --------
DIM 単位行列(N,N)    ! =E
DIM 遷移確率(N,N)    ! =B
DIM 期待値(N)
MAT 期待値=ZER(N)

FOR 出揃い数=K TO N
   LET  R=出揃い数
   ! ---- 遷移確率行列作成 ----
   LET 最下行=R-K+1
   MAT 遷移確率=ZER(最下行,最下行)
   MAT 単位行列=IDN(最下行)
   FOR J=K TO 出揃い数-1
      LET  列番=J-K+1
      LET  遷移確率(最下行,列番)=1
      FOR I=J TO J+K
         IF I<出揃い数 THEN
            LET  行番=I-K+1
            LET  新規=I-J      ! =D 
            LET  遷移確率(行番,列番)=組合せ数(N-J,新規)*組合せ数(J,K-新規)/組合せ数(N,K)
            LET  遷移確率(最下行,列番)=遷移確率(最下行,列番)-遷移確率(行番,列番)
         END IF
      NEXT I
   NEXT J 
   ! ---- 期待値計算 ----
   MAT  遷移確率=遷移確率-単位行列    ! =B-E  メモリ節約 
   MAT  遷移確率=INV(遷移確率)        ! =B^-1    
   MAT  遷移確率=遷移確率*遷移確率    ! =B^-2
   LET  期待値(出揃い数)=遷移確率(最下行,1)
   PRINT USING "N=###   K=###   R=###    期待値(R)=":N,K,R;
   PRINT 期待値(R)  
NEXT  出揃い数

IF K=1 THEN CALL グラフ初期化(N)
SET LINE COLOR K
SET POINT COLOR K
CALL  グラフ(期待値,N,K)

END

EXTERNAL FUNCTION 組合せ数(N,r)
IF r<0 OR r>N THEN 
   LET  C=0
ELSE
   LET  C=1
   FOR k=1 TO r
      LET  C=C*(N-k+1)/K
   NEXT k
END IF 
LET  組合せ数=C
END FUNCTION

EXTERNAL SUB グラフ初期化(N)
CLEAR
SET COLOR MIX(15)  0.5,0.8,0.5
SET WINDOW -1,N+1,-2,3*N
DRAW GRID(1,5)
SET WINDOW 0,1,0,1
PLOT TEXT ,AT 0.2,0.9:"N=" & STR$(N) & "     K"
END SUB

EXTERNAL SUB グラフ(E(),N,K)
DIM X(N-K+2),Y(N-K+2)
LET  Y(1)=0
LET  X(1)=K-1
FOR i=K TO N
   LET  X(i-K+2)=i
   LET  Y(I-K+2)=E(i)
NEXT I

SET WINDOW -1,N+1,-2,3*N
SET POINT STYLE 4

MAT  PLOT LINES:X,Y
MAT  PLOT POINTS:X,Y

SET WINDOW 0,1,0,1
PLOT LINES:0.2,0.9-0.03*K;0.3,0.9-0.03*K
PLOT TEXT ,AT 0.31,0.885-0.03*K: STR$(K)
END SUB

下記は計算結果です。

　『出揃うまでの回数』へ

　数学の部屋へもどる