Sleeping beauty problem IV

Previous post in this series

I have been waiting to see some conclusions coming from discussions of the problem at the Stubborn Mule blog, however the discussion seems to have petered out without a final statement. I admit I did not read the details of Giulio Katis's mathematical model, even though it was very closely related to the (sequential part of ) the compositional model of Markov chains that de Francesco Albasini, Sabadini and I developed in "The Compositional Construction of Markov Processes, Applied Categorical Structures 2011",  "The Compositional Construction of Markov Processes II, RAIRO - Theor. Inf. and Applic., 2011", and in Luisa's PhD thesis at the University of Insubria, Como, 2011.

However I remain convinced that the matter is simple and I would like to make a couple of mathematical comments.



A Markov chain is usually described as a particular type of stochastic process. However a simpler starting point is to consider a finite set of states, $\{ 0,1,2,\cdots k \}$ say,and for each pair of states $(i,j)$ a $probability$ $a_{i,j}$ $of\; the\; transition$ from $i$ to $j$, which probabilities form a $k\times k$ matrix $A$ whose row sums are all $1$, a stochastic matrix.

It is then easy to see that $A^n$ also has row sum $1$, and we may identify the the $(i,j)$ element as the $probability\; of\; an\; n\; step\; transition$ from $i$ to $j$. This is a $definition$, not a theorem in this context. (It may be made a theorem about a stochastic process derived from $A$, but the (rather difficult) construction of a stochastic process from a matrix involves essentially using the matrix product.)

Notice however that there are other row-sum-$1$ matrices related to $A$, for example $1/2(A + A^2)$. What I suggested in the first post in this series is that the $(i,j)$th element of this matrix might be identified with the $probability\; of\; a\; one-{\bf or}-two\; step\; transition$ from $i$ to $j$. Again this is a possible definition, not a theorem. Another example; the matrix $(I+A+A^2+\cdots +A^n)/(n+1)$ is a row-sum-$1$ matrix, which may be identified as the probability of a transition from $i$ to $j$ in from $0$ to $n$ steps.

Suppose now we accept the sense of these definitions, let us look at the transition system in the first post in this series, and the corresponding $5\times 5$ matrix $A$. To apply the mathematics, I claim that the sleeping beauty needs to make two calculations: (i) what is the probability that she has passed from state $0$ to $1$ in one step? and (ii) what is the probability that she has passed from state $0$ to state $3$ or state $4$ in one-or-two steps? The first step uses the matrix $A$ and results in $1/2$. For the second the matrix $1/2(A+A^2)$ yields a probability of $1/4$ for the probability of passing from $0$ to $3$ in one or two steps, and $1/4$ for passing from $0$ to $4$ in one or two steps, and hence a probability of $1/2$ for passing from $0$ to $3$ or $4$ in one or two steps.

Her answer to the question of whether the coin was heads should be $1/2$.

Notice that the matrix  $(I+A+A^2+\cdots +A^n)/(n+1)$ tends to a limit as $n$ tends to $\infty$ (see [2] for a proof), the limit being a row-sum-$1$ matrix whose $(i,j)$th entry might be defined to be the probability of passing from $i$ to $j$ in any number of steps.


[1] Charles M. Grinstead and J. Laurie Snell. Introduction to Probability: Second Revised Edition. American Mathematical Society, 1997.

[2] Carl D. Meyer, Matrix Analysis and Applied Linear Algebra, SIAM: Society for Industrial and Applied Mathematics, 2001.

[3] E. Seneta, Non-negative Matrices and Markov Chains, Springer Series in Statistics, 1973,