Monday, November 10, 2014

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,



Blogger Giulio Katis said...


Why do you think this problem (and all the variants it has spawned) has attracted so much attention? Do you think a specific calculation will make sense of the confusion that surrounds it?

It would seem to me that instead certain explicit general concepts need to be identified. One of these I believe is the notion of restricting an experiment to only being in a subset of its states. You can find a definition of this (along with other relevant concepts) in my note - which is a complete rewrite of the note of mine that was originally published on Stubborn Mule (parts of my thinking have been clarified since then). I would be interested in your comments.

One last question: if you really think this problem is so simple, why have you written (to date) four blogs on it?

Regards from Down Under,

3:43 AM  

Post a Comment

<< Home