賭ケグルイ双.three-hit-dice.期待値.simulation.rb

#!/usr/bin/env ruby
# coding: utf-8

N=100 # infty
def gen
  ar = N.times.map{ %w(U D)[rand(2)]}.join '' # infinite seq
  memo = {}
  for i in 0..(N-3)
    sub = ar[i..i+2]
    memo[sub] = i + 1 if memo[sub] == nil
    break if memo.size == 8
  end
  memo
end

M=20000 # trial times
count={}
M.times {
  m = gen
  for k in m.keys
    count[k] = 0 if count[k] == nil
    count[k] += m[k]
  end
}
for k in count.keys
  puts "#{k} #{count[k] / M.to_f}"
end

Simulated Expected Time (exclusive)

   time ruby test.rb | sort 
DDD 11.9241
DDU 5.96515
DUD 8.052
DUU 5.994
UDD 6.0393
UDU 8.0452
UUD 5.96445
UUU 11.9394
ruby test.rb  1.30s user 0.00s system 99% cpu 1.298 total
sort  0.00s user 0.00s system 0% cpu 1.298 total

考察.

部分文字列 w について、 w を部分文字列として含まない長さmの文字列の数をC(m; w) とする.

C(m; UUU) と C(m; DDD) は1,2,4 で始まるtri-bonacci
そうでないときは、微妙にアレンジされたtri-bonacci よくわからん？！

w=DUU
for i in {U,D}; do echo $i; done | grep -v $w | wc -l
for i in {U,D}{U,D}; do echo $i; done | grep -v $w | wc -l
for i in {U,D}{U,D}{U,D}; do echo $i; done | grep -v $w | wc -l
for i in {U,D}{U,D}{U,D}{U,D}; do echo $i; done | grep -v $w | wc -l
for i in {U,D}{U,D}{U,D}{U,D}{U,D}; do echo $i; done | grep -v $w | wc -l
for i in {U,D}{U,D}{U,D}{U,D}{U,D}{U,D}; do echo $i; done | grep -v $w | wc -l
for i in {U,D}{U,D}{U,D}{U,D}{U,D}{U,D}{U,D}; do echo $i; done | grep -v $w | wc -l

アルファベット {U,D} 上の文字列を考える.
無限長の文字列 s (=s[1],s[2],...) 中に有限長文字列 w が m番目に現れるとは、

1. (s[m], s[m+1] .., s[m+|w|-1]) = w であってかつ、
2. (s[1], s[2], .., s[m+|w|-2]) は部分文字列として w を持たないこと

例. s=DUUUDDDUDUDUDU 中に DUD は7番目に出現する (たぶん漫画とは数え方が微妙に異なる)

問題. 長さ3のwが何番目に出現するか、sが一様分布で与えられる下でその期待値を求めよ.