桃鉄ハワイで、ゴールするまで何回さいころを振るかの期待値
注目度
17
閲覧数
9056
未解決
暇なときに
Check
このエントリーをはてなブックマークに追加
citacita
(0pt)

桃鉄は、すごろくゲームと考えて下さい。
（桃鉄のハワイのように行き止まりがゴールの場合についての問題です。）

すごろくと異なるのは、ゴール（上がり）をユーターンして駒を動かすことができないことです。

すごろくの升目を、ゴール（上がり）はＧ、それに近い順にＡ１、Ａ２、Ａ３、Ａ４、Ａ５、Ａ６、……とします。

今Ａ３に駒があり、さいころを振ったら５が出たとき、
通常のすごろくならば、Ａ３→Ａ２→Ａ１→Ｇ→Ａ１→Ａ２　と進むことができます
しかし桃鉄の場合は、ユーターンができないので、Ａ３→Ａ４→Ａ５→Ａ６→Ａ７→Ａ８としか進めません

このとき一般的にＡiに駒があるときに、最善手でこまを進めてときに、ゴールするまでさいころを振る回数の期待値はどのように求めればいいのでしょうか？



※通常のすごろくのルールならば、Ａ１、Ａ２、Ａ３、Ａ４、Ａ５、Ａ６に駒がある時点ならば、無限逃避級数を用いて、簡単に６回であることも求められています。

※Ａ４に駒があり、１の目が出たとき、Ａ３とＡ５のどちらに移動するのが最善手なのかも分かってはいません。（感覚的には、Ａ３なのですが）

※進める数が1または２である場合（例えばコインを投げて表2マス、裏1マス）の場合は、下記の連立方程式で求めました。（正しいかどうかわかりませんが）
この場合、Ａ２に駒がありさいころの目が１のとき、明らかにＡ３よりもＡ１に進めるほうが最善手であることがいえるから立てれた式です。

　　　Ａ１の期待値ｘ　Ａ２の期待値ｙ　Ａ３の期待値ｚ　として
　　　ｘ＝１／２＋（ｚ＋１）／２　　　ｙ＝１／２＋（ｘ＋１）／２　　ｚ＝（ｘ＋１）／２＋（ｙ＋１）／２


※実際の桃鉄は、もちろん様々な要素（升目の色や季節等）を考えて進めますが、もちろんこの問題では、それらを無視してください。

2010-07-28 23:13:58
前へ　 1 | 2　
oshinobi
(36pt)
すいません、この連休ずっと考えてもまだ解けていませんが、途中経過報告です。

x_{1}～x_{n} の中の最小値、および順番を求める手順ですが、
私が考えている方針は、yo1928さんがすでに指摘している主張

 1) \forall i \in [1,n], \forall j \in [n+1,2n-1], x_{i} \le x_{j}
 2) x_{n+1} \le x_{n+2} \le x_{n+3} \le \cdots

これを示し、さらに i \in [1,n], j \in [n+1,2n-1] に対して \alpha \le x_{i} \le \beta < \gamma \le x_{j} \le \delta なる\alpha, \beta, \gamma, \delta を見つける評価を行った上で、
『Aiから駒を動かすときに、A1～An の間から外に飛び出してしまう確率が高いほど、x_{i} が大きくなる』という推論が正しいかどうか、調べようとしています。

したがってまず、上記の主張1),2)が正しいことを証明したいわけですが、これですらまだできていません。

せめて以下に、今わかっていることを、列挙いたします。
（証明は、今回は省略します（長ったらしくなるため）が、リクエストあれば載せます。）

----
☆【仮定】An 以遠に駒があるときは、出た目にかかわらず必ず前進するものとします。

■すべての i に対して、x_{i} \ge n . すなわち、 \alpha \ge n .
  さらに i \ge n+1 なら x_{i} \ge n+1 .
■x_{n} = \frac{1}{n} \sum_{i=1}^{n-1} x_{i} + 1
■x_{n+1} = \frac{1}{n} \sum_{i=1}^{n} x_{i} + 1 = \bar{x} + 1 = \frac{n+1}{n} x_{n} .
  （ \bar{x} \equiv \frac{1}{n} \sum_{i=1}^{n} x_{i} と定義）

■x_{1}, \cdots, x_{2n-1} を小さい順に並べたものを y_{1}, \cdots, y_{2n-1} とする。
  主張1)が成り立たない場合、すなわち y_{k} (k \le n-1) まで = x_{i} (i \in [1,n]) で、
  y_{k+1} = x_{j} (j \in [n+1,2n-1]) となってしまうとき、
  y_{k+1} = x_{j} \ge \frac{1}{k} \sum_{p=1}^{k} y_{p} + \frac{n}{k} .
  （つまり k+1番目の数は、それまでの k 個の数の平均より 1 以上大きくなってしまう）

■とりあえず実験として、n=12 でも計算してみました。
  すると主張1),2) の通りの結果がでました。
   x_{12}(\simeq 15.54) < x_{1} < \cdots < x_{6}(\simeq 16.12) < x_{13}(\simeq 16.83) < x_{14} \cdots < x_{23}(\simeq 18.04)
■なので、各 x_{i} の評価について \alpha \sim 1.25\,n,\ \beta \sim 1.35\,n,\ \gamma \sim 1.40\,n くらいと予想しています。（\delta は、よくわからない…）

----

＃長文になりまして、すみません。引き続き、がんばります。
＃あと誰か、 ☆ が妥当か（すなわち x_{n+1} \le x_{n+2} \le \cdots \le x_{2n-1} \le x_{2n} \le \cdots か？）教えて…

1拍手 |
2010-09-21 23:38:52
oshinobi
(36pt)
さんざん考えてきましたが、わたし個人の力では解ききれませんでした。
力が及ばず、本当にごめんなさい。
やっぱり、最善手の選択というのがあって、すっきり方程式を決められないために、扱いが複雑であるのが要因です。

すなわち、方程式を書きますと、
 x_{1}=\frac{1}{n}(x_{3}+x_{4}+\cdots+x_{n}+x_{n+1})+1
と x_{1} はいいのですが、x_{2} 以降は、
 x_{2}=\frac{1}{n}(\min\{x_{1},x_{3}\}+x_{5}+\cdots+x_{n+2})+1
 x_{3}=\frac{1}{n}(\min\{x_{2},x_{4}\}+\min\{x_{1},x_{5}\}+x_{7}+\cdots+x_{n+3})+1
…となって、大小関係がわからないと決められません。
なお、『（☆）An 以遠に駒があるときは、出た目にかかわらず必ず前進する』ものと仮定すると、 x_{n} 以降の方程式は次のようになります：
 x_{n}=\frac{1}{n}(x_{1}+x_{2}+\cdots+x_{n-1})+1
 x_{n+1}=\frac{1}{n}(x_{1}+x_{2}+\cdots+x_{n})+1
 x_{n+2}=\frac{1}{n}(x_{2}+x_{3}+\cdots+x_{n+1})+1 , …

さてこれらの連立方程式から、先日記した主張1),2) を導きたいわけですが、
せめて今までにわかったことを書きます。
もしかしたら、本当の正解へのヒントが隠されているのかも知れません。

■1 \le i \le n-1 に対して x_{i}<x_{n+i} 。
（証明）一例として x_{2}<x_{n+2} を示す。
 x_{2} は方程式が定まっていないが、\min\{x_{1},x_{3}\} に対して \le x_{1},\ \le x_{3} の両方が成り立つので
 x_{2}\le\frac{1}{n}(x_{3}+x_{5}+\cdots+x_{n+2})+1
 一方 x_{n+2} の方程式は上記の通りなので、
 x_{n+2}-x_{2} \ge \frac{1}{n}(x_{2}+x_{4}-x_{n+2})
 \frac{n+1}{n}(x_{n+2}-x_{2}) \ge \frac{1}{n}x_{4}>0 （終）

■ x_{n+1}<x_{n+2}<\cdots<x_{2n-1} 【主張2)】。
（証明）1 \le i \le n-2 に対して、
 x_{n+i+1}-x_{n+i} = \frac{1}{n}(x_{n+i}-x_{i})>0 （終）

■x_{n+p}\ (1 \le p \le n-1) を x_{1} ～ x_{n} で表すと、
  x_{n+p} = \frac{(n+1)^{p-1}}{n^{p}}(x_{1}+\cdots+x_{n}) - \sum_{j=1}^{p-1} \frac{(n+1)^{p-j-1}}{n^{p-j}}x_{j} + \left( \frac{n+1}{n} \right)^{p-1} 。
   ※なお、上の式の x_{1} ～ x_{n} の係数の和は 1 になる。
（証明）数学的帰納法で証明が可能。すいませんが、詳細は省略します。

■ x_{1} ～ x_{n}  の中の最小値を m, 最大値を M  とおくと、
 m \ge \frac{e+2}{4}n(\sim 1.180\, n) ,\ M \le \sqrt{e}\,n(\sim 1.649\,n) 。
 （ただし、x_{n} が最小と予測します）
（証明）　（ここでは n が偶数の場合について記します。）
上の等式を使って、
 x_{1}=\frac{1}{n}(x_{3}+\cdots+x_{n}+x_{n+1})+1
    =\frac{1}{n^2}x_{1}+\frac{1}{n^2}x_{2}+\frac{n+1}{n^2}x_{3}\cdots+\frac{n+1}{n^2}x_{n}+\frac{n+1}{n}
 x_{2}=\frac{1}{n}(\min\{x_{1},x_{3}\}+x_{5}\cdots+x_{n+2})+1
   =(\square x_{1}+\cdots+\square x_{n}) + 1 + \frac{1}{n} \left(1+\frac{n+1}{n} \right)
   =(\square x_{1}+\cdots+\square x_{n}) + \left(\frac{n+1}{n} \right)^{2}
  ※上の\squareに入る数字は、\min\{x_{1},x_{3}\} の選択があるため、決まっていない。
     ただしこれらの係数の和は、必ず \frac{n-1}{n} になる。
同様にして
 x_{p}=(\square x_{1}+\cdots+\square x_{n}) + \left(\frac{n+1}{n} \right)^{p} \quad (\text{if } 1 \le p \le n/2)　
 x_{p}=(\square x_{1}+\cdots+\square x_{n}) + \left(\frac{n+1}{n} \right)^{p} - \left(\frac{n+1}{n} \right)^{2p-n} + 1 \quad (\text{if } n/2 < p < n)　
さて、x_{1}.\cdots,x_{n} \ge m より、各式の係数の和が \frac{n-1}{n} であることに注意すると、
 x_{p} \ge \frac{n-1}{n}m + \left(\frac{n+1}{n} \right)^{p} \quad (\text{if } 1 \le p \le n/2)
 x_{p} \ge \frac{n-1}{n}m + \left(\frac{n+1}{n} \right)^{p} - \left(\frac{n+1}{n} \right)^{2p-n} + 1 \quad (\text{if } n/2 < p < n)
x_{n}=\tfrac{1}{n}(x_{1}+\cdots+x_{n-1})+1 に、上記不等式を代入すると、
 x_{n} \ge \left(\frac{n-1}{n}\right)^{2}m + \frac{n+1}{2n+1}\left(\frac{n+1}{n}\right)^{n}+\frac{4n^{2}-3n-2}{2n(2n+1)}
x_{n}=m であるとするならば、
 \frac{2n-1}{n^2}m \ge \frac{n+1}{2n+1}\left(\frac{n+1}{n}\right)^{n}+\frac{4n^{2}-3n-2}{2n(2n+1)}
 n：十分大にて m \ge \frac{n}{2} \left(\frac{1}{2}e+1\right) \sim \frac{e+2}{4}n　.

また最大値について考えると、 x_{1}.\cdots,x_{n} \le M であり、また x_{1},\cdots,x_{n-1} のどれかが M なので、各 x_{p} を =M とおいた不等式
 M \le \frac{n-1}{n}M + \left(\frac{n+1}{n} \right)^{p} \quad (1 \le p \le n/2)
 M \le \frac{n-1}{n}M + \left(\frac{n+1}{n} \right)^{p} - \left(\frac{n+1}{n} \right)^{2p-n} + 1 \quad (n/2 < p < n)
これらのうち、どれか1つ以上が成り立たなければならない。
定数部分の最大値は \left(\frac{n+1}{n} \right)^{n/2}であることから、
少なくとも \frac{1}{n}M \le \left(\frac{n+1}{n} \right)^{n/2}でなければならない。
 n が十分大であるとき、M \le \left(\frac{n+1}{n} \right)^{n/2}n \sim \sqrt{e}\,n が成り立つ。（終）

----------

私が調べられたのは、以上です。

ここまで調べてきてなんなのですが、ちょっと違った方針で考えた方がよかったかな、という気もしました。

＃例えば、いくつか数値実験した結果から、x_{1} ～ x_{n} の値の最小値と最大値の差は
   1 未満となると予想しています。
  もしもこれを示すことができれば、【主張1)】を示すには十分ですし、各期待値 x_{i} の
  大小を比較することもすぐにできると思います。

1拍手 |
2010-10-03 15:59:44
natrium
(84pt)
この問題に関して、数学的に考察するのは私には難しそうなので、
プログラムを組んで、コンピュータにシミュレーションをさせてみました。
みなさんの思考の一助となれれば幸いです。

方法は以下の通りです。
① 1～nまでの値の順列Pを生成する
② 各順列に対して、P_i<P_{i+1} ならばx_i>x_{i+1}と仮定し、その優先順位に従って複数回シミュレーションを行なう
③ シミュレーションの結果、各マスのあがりへ移動するのに必要な手数の平均値が生成した順列(の逆順)と同じ並び順になっていたら、その順列は確率的に正しい序列の候補である判定する

※i>nなるx_iに関しては「あがりに近づく方に動いたほうが良い」と仮定しています。
※ 複数の異なる順列に対してそれと同じ並び順の平均値の大小関係が得られた場合は、候補が複数あることになります。
※n=6の時の結果をoshinobiさんの理論値と比較する限り、平均値の有効桁数は上から2～3桁程度のようです。

n=1
試行回数：200万回
候補：1通り

x_{1}

\begin{array}{|l|l|l|l|} \hline {x_{1}} & 1.000000 & & \\ \hline \end{array}

n=2
試行回数：200万回
候補：1通り

x_{2}<x_{1}

\begin{array}{|l|l|l|l|} \hline {x_{1}} & 2.797537 & x_{3} & 3.596595 \\ \hline {x_{2}} & 2.399570 & & \\ \hline \end{array}

n=3
試行回数：200万回
候補：1通り

x_{3}<x_{1}<x_{2}

\begin{array}{|l|l|l|l|} \hline {x_{1}} & 3.750914 & x_{4} & 4.712611 \\ \hline {x_{2}} & 3.856626 & x_{5} & 5.035202 \\ \hline {x_{3}} & 3.535299 & & \\ \hline \end{array}

n=4
試行回数：200万回
候補：1通り

x_{4}<x_{1}<x_{3}<x_{2}

\begin{array}{|l|l|l|l|} \hline {x_{1}} & 5.034508 & x_{5} & 6.111314 \\ \hline {x_{2}} & 5.376923 & x_{6} & 6.366888 \\ \hline {x_{3}} & 5.136764 & x_{7} & 6.624046 \\ \hline {x_{4}} & 4.887062 & & \\ \hline \end{array}

n=5
試行回数：200万回
候補：1通り

x_{5}<x_{1}<x_{4}<x_{2}<x_{3}

\begin{array}{|l|l|l|l|} \hline {x_{1}} & 6.313954 & x_{6} & 7.392890 \\ \hline {x_{2}} & 6.499213 & x_{7} & 7.614170 \\ \hline {x_{3}} & 6.600240 & x_{8} & 7.833229 \\ \hline {x_{4}} & 6.413340 & x_{9} & 8.091016 \\ \hline {x_{5}} & 6.165030 & & \\ \hline \end{array}

n=6
試行回数：200万回
候補：1通り

x_{6}<x_{1}<x_{5}<x_{2}<x_{4}<x_{3}

\begin{array}{|l|l|l|l|} \hline {x_{1}} & 7.713265 & x_{7} & 8.829950 \\ \hline {x_{2}} & 7.829038 & x_{8} & 9.022221 \\ \hline {x_{3}} & 8.098841 & x_{9} & 9.220260 \\ \hline {x_{4}} & 7.960234 & x_{10} & 9.409611 \\ \hline {x_{5}} & 7.800771 & x_{11} & 9.609674 \\ \hline {x_{6}} & 7.567874 & & \\ \hline \end{array}

n=7
試行回数：20万回
候補：1通り

x_{7}<x_{1}<x_{2}<x_{6}<x_{5}<x_{3}<x_{4}

\begin{array}{|l|l|l|l|} \hline {x_{1}} & 9.002963 & x_{8} & 10.066649 \\ \hline {x_{2}} & 9.036184 & x_{9} & 10.248216 \\ \hline {x_{3}} & 9.245218 & x_{10} & 10.422635 \\ \hline {x_{4}} & 9.330149 & x_{11} & 10.647820 \\ \hline {x_{5}} & 9.209259 & x_{12} & 10.777289 \\ \hline {x_{6}} & 9.059803 & x_{13} & 10.881609 \\ \hline {x_{7}} & 8.845881 & & \\ \hline \end{array}


n=1..6 のパターンから考えるに、 n=7 のx_{2}とx_{6}は逆な気がします。
nを増やすと計算量が急激に増加するので、試行回数を減らした弊害かも知れません。

とりあえずなんとなく共通して見えているのは、
x_{n}<x_1<x_{n-1}<x_2\cdots<x_{n-i}<x_{i+1}<\cdots<x_{\left\lceil \frac{n}{2} \right\rceil}<x_{n+1}<x_{n+2}<\cdots<x_{n+j}<x_{n+j+1}<\cdots
という序列ですかね。
4拍手 |
2011-01-25 00:55:34
wosugi
(12pt)
オートマトンを考えてプログラミングで解いたところ、期待値は 8.207 回になりました。
解法は↓のとおりです。

仮定として、移動の際は、可能なかぎりゴールに近づくことにします。
k 回サイコロを振ったときに A_i にいる確率を p_i^{(k)} と表記します（ A_0 をゴールとします）。
また、その列ベクトルの表現を {\bm p}^{(k)} とします。
{\bm p}^{(0)} は p_3^{(0)}=1 で、それ以外は0です。

遷移確率行列は↓となります。
{\bm Q}^t=\frac{1}{6} \begin{pmatrix} 6,0,0,0,0,0,0,0,0,0,0,0 \\ 1,0,0,1,1,1,1,1,0,0,0,0 \\ 1,1,0,0,0,1,1,1,1,0,0,0 \\ 1,1,1,0,0,0,0,1,1,1,0,0 \\ 1,1,1,1,0,0,0,0,0,1,1,0 \\ 1,1,1,1,1,0,0,0,0,0,0,1 \\ 1,1,1,1,1,1,0,0,0,0,0,0 \\ 0,1,1,1,1,1,1,0,0,0,0,0 \\ 0,0,1,1,1,1,1,1,0,0,0,0 \\ 0,0,0,1,1,1,1,1,1,0,0,0 \\ 0,0,0,0,1,1,1,1,1,1,0,0 \\ 0,0,0,0,0,1,1,1,1,1,1,0 \end{pmatrix}

遷移は次式となります。
{\bm p}^{(k+1)}={\bm Q}^t{\bm p}^{(k)}

当然ながら  p_0^{(\infty)}=1です。

遷移確率行列内の「6」の部分を「0」とすれば、
p_0^{(k)}が k 回目でゴールに着いた確率になるので、
それを列挙しますと↓になります。
 
01:  0.1666666667
02:  0.0555555556
03:  0.1018518519
04:  0.0871913580
05:  0.0668724280
06:  0.0640646433
07:  0.0549447016
08:  0.0482532912
09:  0.0427500492
10:  0.0374518805
 
m=\sum_{k=1}^{\infty} kp_0^{(k)}が求めたい答えになります。

数値解なので微妙ですが、解析の参考になれば幸いです。
2拍手 |
2011-01-25 21:19:48
前へ　 1 | 2　
一言投稿 (Ｑ＆Ａに関して、思ったことなどをつぶやいてみよう！)
oshinobi　 本問のやり取りは、回答順に読んでほしいので、興味をもった方は「前へ」（または「1」）のリンクをクリックしてください。　 (11/1/14)
inokoj　 おもしろい！！　 (10/12/6)
hello　 こんなに議論される問題もあるんですね。　 (10/12/4)

そのままでしばらくお待ちください


しばらくたっても変わらない場合はキャンセルしてください

キャンセル

以下の内容で回答を投稿します

よろしいですか？

回答内容

回答の投稿が完了しました

こちらからご確認ください