<pre>
Q: You have a cube with two sides painted red.  You roll the cube N times.
What is the probability that you will have rolled "red" on at least two
consecutive throws?


A: Let u(N) be the probability in N throws of having no two consecutive
reds, and ending on a non-red; v(N) the probability in N throws of having
no two consecutive reds and ending on a red.  Let X(N) be the vector

<pre>
 ~[[u(N)]]               ~[[ 2/3 ]]                               ~[[ 2/3  2/3 ]]
 ~[[v(N)]].  Then X(1) <code> ~[[ 1/3 ]] and X(N+1) </code> M X(N) where M = ~[[ 1/3   0  ]].
</pre>

Using the diagonalization M = V D V^(-1) where

<pre>
    ~[[ 3 r1   3 r2 ]]         ~[[ r1  0 ]]
 V <code> ~[[   1      1  ]] and D </code> ~[[ 0 r2 ]],

 r1 = (1+sqrt(3))/3,
 r2 = (1-sqrt(3))/3.
</pre>

We get

<pre>
        ~[[ (sqrt(3)+3) r1^n/6 + (3-sqrt(3)) r2^n/6 ]]
 X(N) = ~[[     sqrt(3) r1^n/6 - sqrt(3) r2^n/6 ]]
</pre>

and your probability is

<pre>
 1 - u(N) - v(N) = 1 - r1^n (1/2+sqrt(3)/3) - r2^n (1/2-sqrt(3)/3)

 Robert Israel                                israel@math.ubc.ca
 Department of Mathematics        http://www.math.ubc.ca/~israel
 University of British Columbia
 Vancouver, BC, Canada V6T 1Z2

 Here are the first twenty values of this probability:

 0: 0/1 = 0
 1: 0/3 = 0
 2: 1/9 = 0.111111
 3: 5/27 = 0.185185
 4: 21/81 = 0.259259
 5: 79/243 = 0.325103
 6: 281/729 = 0.38546
 7: 963/2187 = 0.440329
 8: 3217/6561 = 0.490322
 9: 10547/19683 = 0.535843
 10: 34089/59049 = 0.5773
 11: 108955/177147 = 0.615054
 12: 345137/531441 = 0.649436
 13: 1085331/1594323 = 0.680747
 14: 3392377/4782969 = 0.709262
 15: 10549739/14348907 = 0.735229
 16: 32667201/43046721 = 0.758878
 17: 100782787/129140163 = 0.780414
 18: 309946697/387420489 = 0.800027
 19: 950599131/1162261467 = 0.817888
</pre>

Here is how to solve this problem using Mathematica:

<< Discrete-Math`RSolve`

<pre>
 RSolve~[[{u~[n]] <code></code> 2/3 u~[[n - 1]] + 2/3 v~[[n - 1]],
   v~[[n]] <code></code> 1/3 u~[[n - 1]],
   u~[[1]] <code></code> 2/3,
   v~[[1]] <code></code> 1/3},
   {u, v}, n]]
</pre>
</pre>
