150603

Ruby


塊の個数

「ホワイト・ブロック」問題（http://riverplus.net/misc/20150531/）

とほとんど変わらないが、次の問題を考える。

m 色の石を n 個並べるとき、連続した石の塊の個数の期待値を

求めよ。

E(n + 1) = (E(n) + 1) × (m - 1) / m + E(n) × 1 / m = E(n) + (m - 1) / m

E(1) = 1

より、

E(n) = ((m - 1) n + 1) / m

と求まるが、

あえて地道に数える方法は以下のとおりである。

# （色を区別せず）塊を数える

def cnt(ary)

  s = 1

  ary.each_cons(2){|a| s += 1 if !(a[0] == a[1])}

  s

end

m, n = 2, 6

sum, x = 0, 0

(1..m).to_a.repeated_permutation(n){|c|

  sum += cnt(c)

  x += 1

}

# 塊の個数の期待値

p (sum + 0.0) / x

出力結果

3.5