On the rechargeable Polya urn scheme and Blackwell's conjecture for Hidden Markov Models

ABSTRACT

Consider an urn which at time n=0 has B(0) blue balls and G(0) yellow balls. A times n=1,2,..., choose a ball at random, look at it, return it and add another ball of the same colour. Let B(n) and G(n) denote the number of balls at time n and let Y(n) denote the colour of the ball chosen at time n. Let X(n)=(B(n),G(n)). Clearly X(n), n=0,1,2,... is a Markov chain. (An example of a Polya urn scheme). Let us now change the procedure in such a way that before we draw a new ball there is a fixed probability c that we restart the process with one blue ball and one yellow ball. As above, let B(n),G(n) denote the number of blue and yellow balls at time n, let Y(n) be the colour of the ball drawn at time n, and let X(n)=(B(n),G(n)). Clearly X(n),n=0,1,2,... and Y(n), n=1,2,.. can be considered respectively as the state sequence and the observation sequence of a Hidden Markov Model. (This is called the rechargeable Polya urn scheme). Now, let Z(n) be the conditional distribution of X(n) given the colour observations Y(1),Y(2),...,Y(n), and let mu(n) denote the distribution of Z(n). The purpose of this talk is to indicate a proof of the fact that mu(n) converges in distribution towards a unique limt measure. (Not very sur-prising.) In order to motivate the just mentioned result I shall first however discuss Blackwell’s conjecture from 1957 regarding the existence of a unique invariant measure for the sequence of conditional distributions associated to a Hidden Morkov Model and briefly present what I believe is known regarding Blackwell’s conjecture up to today.