No.1501
駒が \(i\) の位置にあるとき, 最終的に駒が \(N\) にたどり着く確率を \(p_i\) とすると,
\[\begin{align} p_1 &= 0 \\ p_2 &= b_2 p_3 \\ p_3 &= a_3 p_2 + b_3 p_4 \\ & \vdots \\ p_{N-2} &= a_{N-2} p_{N-3} + b_{N-2} p_{N-1} \\ p_{N-1} &= a_{N-1} p_{N-2} + b_{N-1} \\ p_N &= 1 \end{align}\]となる. ただし,
\[\begin{align} a_i &= \frac{ A_{i-1} }{ A_{i-1} + A_{i+1} } \\ b_i &= \frac{ A_{i+1} }{ A_{i-1} + A_{i+1} } \end{align}\]である. これを上の式から順に解いていくと,
\[\begin{align} p_2 &= b_2 p_3 = c_2 p_3 \\ p_3 &= \frac{b_3}{1 - a_3 c_2} p_4 = c_3 p_4 \\ p_4 &= \frac{b_4}{1 - a_4 c_3} p_5 = c_4 p_5 \\ & \vdots \\ p_{N-2} &= \frac{ b_{N-2} }{ 1 - a_{N-2} c_{N-3} } p_{N-1} = c_{N-2} p_{N-1} \\ p_{N-1} &= \frac{ b_{N-1} }{ 1 - a_{N-1} c_{N-2} } = c_{N-1} \end{align}\]となって \(p_{N-1}\) が求められる. ただし,
\[\begin{align} c_2 &= b_2 \\ c_i &= \frac{b_i}{ 1 - a_i c_{i-1} } \end{align}\]である. ここから \(p_K\) は,
\[p_K = c_K p_{K+1} = c_K c_{K+1} p_{K+2} = \dots = c_K c_{K+1} \dots c_{N-1}\]で求めることができる.