六面体の頂点をたどる（1）

今年の京大2問目、

正四面体ABCDを考える。点Pは時刻0では頂点Aに位置し、1秒ごとにある頂点から他の3頂点のいずれかに、等しい確率で動くとする。このとき、時刻0から時刻nまでの間に、4頂点A、B、C、Dのすべてに点Pが現れる確率を求めよ。ただしnは1以上の整数とする。
http://nyushi.yomiuri.co.jp/nyushi/honshi/08/k01-22p/1.htm

これは四面体だからやさしいが、六面体だったらどうだろう。

JavaScriptで擬似乱数を使って、100万回シミュレートしてみた。3ヶ所ある隣の点に同確率で移って、すべての点をたどるまで何回かかるかを調べる。たどった点はsにビットを立てる。sが255になったら、8点すべてをたどったことになる。

奇数回のほうが確率が高い。56%が奇数回。
15回が最も確率が高い。
20回増すと、確率が1/10になるようだ。

var neighbor = [

        [ 1, 3, 4 ], [ 2, 1, 5 ], [ 3, 1, 6 ], [ 2, 0, 7 ],

        [ 5, 7, 0 ], [ 6, 4, 1 ], [ 7, 5, 2 ], [ 6, 4, 3 ]

];
var N = 1000000;

var turns = [ ];
for(var i = 0; i < N; i++) {

    add(turns, play());

}
for(var i = 7; i < turns.length; i++) {

    if(turns[i] == undefined)

        turns[i] = 0;

    WScript.Echo(i + "," + (turns[i] / N));

}
function play() {

    var s = 1;

    var pos = 0;

    var t = 0;

    while(s != 255) {

        var r = Math.floor(Math.random() * 3);

        pos = neighbor[pos][r];

        s |= 1 << pos;

        t++;

    }

    

    return t;

}
function add(n, i) {

    if(n[i] == undefined)

        n[i] = 1;

    else

        n[i]++;

}