Celebratio Mathematica

D. H. Blackwell: Some properties of Markoff chains. Ph.D. thesis, University of Illinois at Urbana-Champaign, 1941. Advised by J. L. Doob. MR 2937439 phdthesis

D. Blackwell: “Idempotent Markoff chains,” Ann. Math. (2) 43 : 3 (July 1942), pp. 560–567. MR 0006632 Zbl 0063.00419 article

Let \( \mathcal{B} \) be any Borel field of subsets of an abstract space \( X \), and suppose that for each \( x\in X \) a probability measure \( P(x,E) \) is defined on \( \mathcal{B} \) and that \( P(x,E) \) is for fixed \( E \) a \( \mathcal{B} \)-measurable function of \( x \). Then \( P(x,E) \) may be considered as representing the transition probability of going from the point \( x \) into the set \( E \) in a single trial, and it is said to determine a Markoff chain on \( X \). The probability of going from \( x \) into \( E \) in \( n \) trials, denoted by \( P_n(x,E) \), is given inductively by \begin{equation*}\tag{1} P_n(x,E) = \int P(y,E)\,dP_{n-1}(x,y). \end{equation*} In this paper we shall consider Markoff chains for which \( P_n(x,E) \) is independent of \( n \). It is clear from (1) that this will occur whenever \( P_2(x,E) = P(x, E) \), so that we shall be studying Markoff chains which satisfy \[ P(x,E) = \int P(y,E)\,dP(x,y). \] Such a Markoff chain will be called idempotent, and the justification for this is apparent.

D. Blackwell: “The existence of anormal chains,” Bull. Am. Math. Soc. 51 : 6, Part 1 (1945), pp. 465–468. MR 0011916 Zbl 0063.00420 article

D. Blackwell: “Finite non-homogeneous chains,” Ann. Math. (2) 46 : 4 (October 1945), pp. 594–599. MR 0013858 Zbl 0063.00421 article

Let \( X \) denote the set of integers \( {}1 \), \( 2,\dots \), \( N \), considered as the possible states of a physical system, and denote by \( P_{ij}(r,s) \) the probability that the system is in state \( j \) at time \( s \) under the hypothesis that it is in state \( i \) at time \( r \), where \( r < s \), \( r, s = \dots, -1 \), \( 0,1,\dots \). The \( N{\times}N \) matrices \( P(r,s) \) with elements \( P_{ij}(r,s) \) will be Markoff matrices, i.e. matrices with non-negative elements and row sums unity, and we shall suppose that they satisfy the equation \[ P(r,s)\,P(s,t) = P(r,t) \quad\text{for }r < s < t .\] This equation represents the condition that the successive states of the system form a Markoff chain, i.e. the probability that the system is in state \( j \) at time \( s \) under the hypothesis that it is in state \( i \) at time \( r \) (\( r < s \)) is independent of any hypotheses concerning the states of the system at instants prior to \( r \). A set of \( 1{\times}N \) Markoff matrices \( P(s) \) will be called a set of absolute probabilities if the equation \[ P(s)\,P(s,t) = P(t) \quad\text{for }s < t \] holds. Kolmogoroff [1935] has shown that sets of absolute probabilities always exist and will be unique under certain conditions; it will be easy to show that there are never more than \( N \) linearly independent such sets. Using these facts, together with a theorem of Doob asserting the convergence of a sequence of chance variables satisfying certain conditions, we investigate the asymptotic properties of the matrices \( P(r,s) \) and the associated stochastic processes. Our principal result, Theorem 3, shows that the properties of non-homogeneous chains are analogous to those well known in the homogeneous case where \( P(r,s) \) depends only on \( s - r \).

D. Blackwell: “On transient Markov processes with a countable number of states and stationary transition probabilities,” Ann. Math. Stat. 26 : 4 (1955), pp. 654–658. MR 0075479 Zbl 0066.11303 article

We consider a Markov process \( x_0, x_1, \dots \) with a countable set \( S \) of states and stationary transition probabilities \[ p(t \mid s) = P\{x_{n+1} = t \mid x_n = s\} .\] Call a set \( C \) of states almost closed if

\( P\{x_n \in C\text{ for an infinite number of } n\} > 0 \) and
\( x_n \in C \) infinitely often, implies \( x_n \in C \) for all sufficiently large \( n \), with probability one.

It is shown that there is a set \( (C_1 \), \( C_2, \dots) \) essentially unique, of disjoint almost closed sets such that

all except at most one of the \( C_i \) are atomic, that is, \( C_i \) does not contain two disjoint almost closed subsets,
the non-atomic \( C_i \), if present, contains no atomic subsets,
the process is certain to enter and remain in some set \( C_i \).

A relation between the sets \( C_i \) and the bounded solutions of the system of equations \begin{equation*}\tag{1} \alpha(s) = \sum_t \alpha(t)\,p(t \mid s) \end{equation*} is obtained; in particular there is only one atomic \( C_i \) and no non-atomic \( C_i \) if and only if the only bounded solution of (1) is \( \alpha(t) \) = constant. This condition is shown to hold if the process is the sum of independent identical (numerical or vector) variables; whence, for such a process, the probability of entering a set \( J \) infinitely often is zero or one. The results are new only if the process has transient components. The main tool is the martingale convergence theorem.

D. Blackwell and L. Koopmans: “On the identifiability problem for functions of finite Markov chains,” Ann. Math. Stat. 28 : 4 (1957), pp. 1011–1015. MR 0099081 Zbl 0080.34901 article

Let \( M = \| m_{ij} \| \) be a \( 4{\times}4 \) irreducible aperiodic Markov matrix such that \( h_1 \neq h_2 \), \( h_3 \neq h_4 \), where \( h_i = m_{i1} + m_{i2} \). Let \( x_1 \), \( x_2, \dots \) be a stationary Markov process with transition matrix \( M \), and let \( y_n = 0 \) when \( x_n = 1 \) or 2, \( y_n = 1 \) when \( x_n = 3 \) or 4. For any finite sequence \[ s = (\varepsilon_1\( , \)\varepsilon_2, \dots\( , \)\varepsilon_n) \] of 0s and 1s, let \[ p(s) = \mathrm{Pr}\{y_1 = \varepsilon_1, \dots, y_n = \varepsilon_n\} .\] If \begin{equation*}\tag{1} p^2(00) \neq p(0)\,p(000) \quad\text{and}\quad p^2(01) \neq p(1)\,p(010), \end{equation*} the joint distribution of \( y_1 \), \( y_2, \dots \) is uniquely determined by the eight probabilities \( p(0) \), \( p(00) \), \( p(000) \), \( p(010) \), \( p(0000) \), \( p(0010) \), \( p(0100) \), \( p(0110) \), so that two matrices \( M \) determine the same joint distribution of \( y_1 \), \( y_2, \dots \) whenever the eight probabilities listed agree, provided (1) is satisfied. The method consists in showing that the function \( p \) satisfies the recurrence relation \[ p(s, \varepsilon, \delta, 0) = p(s, \varepsilon, 0)\,a(\varepsilon, \delta) + p(s, \varepsilon)\,b(\varepsilon, \delta) \] for all \( s \) and \( \varepsilon = 0 \) or 1, \( \delta = 0 \) or 1, where \( a(\varepsilon, \delta) \), \( b(\varepsilon, \delta) \) are (easily computed) functions of \( M \), and noting that, if (1) is satisfied, \( a(\varepsilon, \delta) \) and \( b(\varepsilon, \delta) \) are determined by the eight probabilities listed. The class of doubly stochastic matrices yielding the same joint distribution for \( y_1 \), \( y_2, \dots \) is described somewhat more explicitly, and the case of a larger number of states is considered briefly.

D. Blackwell: “Another countable Markov process with only instantaneous states,” Ann. Math. Stat. 29 : 1 (1958), pp. 313–316. MR 0093822 Zbl 0085.12702 article

D. Blackwell and D. Freedman: “The tail \( \sigma \)-field of a Markov chain and a theorem of Orey,” Ann. Math. Stat. 35 : 3 (1964), pp. 1291–1295. MR 0164375 Zbl 0127.35204 article

D. Blackwell and D. Kendall: “The Martin boundary for Pólya’s urn scheme, and an application to stochastic population growth,” J. Appl. Probability 1 : 2 (December 1964), pp. 284–296. MR 0176518 Zbl 0129.10702 article

In 1923 Eggenberger and Pólya [1923] introduced the following “urn scheme” as a model for the development of a contagious phenomenon. A box contains \( b \) black and \( r \) red balls, and a ball is drawn from it at random with “double replacement” (i.e. whatever ball is drawn, it is returned to the box together with a fresh ball of the same colour); the procedure is then continued indefinitely. A slightly more complicated version with \( m \)-fold replacement is sometimes discussed, but it will be sufficient for our purposes to keep \( m=2 \) and it will be convenient further to simplify the scheme by taking \( b = r = 1 \) as the initial condition. We shall however generalise the scheme in another direction by allowing an arbitrary number \( k \) (\( \geq 2 \)) of colours. Thus initially the box will contain \( k \) differently coloured balls and successive random drawings will be followed by double replacement as before. We write \( s^n \) (a \( k \)-vector with \( j \)-th component \( s_j^n \)) for the numerical composition of the box immediately after the \( n \)-th replacement, so that \( s^0 = (1 \), \( 1,\dots \), \( 1) \), and we observe that \( \{s^n: \) \( n=0 \), \( {}1 \), \( 2,\dots\} \) is a Markov proces for which the state-space consists of all ordered \( k \)-ads of positive integers, the (constant) transition-probability matrix having elements determined by \[ Pr\{s^{n+1} = s^n + e(i)\mid s^n\} = \frac{s_i^n}{S^n} ,\] where \( S^n \) is the sum of the components of \( s^n \) and \( (e(i))_j = \delta_{ij} \). We shall calculate the Martin boundary for this Markov process, and point out some applications to stochastic models for population growth.

D. Blackwell and D. Freedman: “On the local behavior of Markov transition probabilities,” Ann. Math. Stat. 39 : 6 (1968), pp. 2123–2127. MR 0233429 Zbl 0175.46903 article

Let \( P(t) = P(t,i,j) \) be a semigroup of stochastic matrices on the countable set \( I = \{i,j,\dots\}. \) Suppose \[ \lim_{t\to 0}P(t,i,i) = 1 \quad\text{for each }i \in I .\] Fix one state \( a \in I \) and abbreviate \( f(t) = P(t,a,a) \).

Suppose \( 0 < \varepsilon < 1 \) and \( f(1) \leq 1 - \varepsilon \). Then \[ \int_0^1 f(t)\,dt < 1 - \tfrac12 \varepsilon.\]

Suppose \( 0 < \varepsilon < 1/4 \) and \( f(1) \geq 1 - \varepsilon \). Then, for all \( t \) in \( [0,1] \), \begin{align*} f(t) &\geq \tfrac12[1 + (1 - 4\varepsilon)^{1/2}]\\ & = 1 - \varepsilon - \varepsilon^2 - O(\varepsilon^3). \end{align*}

Suppose \( 0 < \varepsilon < 1/4 \) and \( \int_0^1 f(t)\, dt \geq 1 - \varepsilon \). Then \[ f(t) > 1 - 2\varepsilon \quad\textit{for }0 \leq t \leq 1 .\]

Note: The last statement can be restated (using algebra) in this more attractive form: if \( 0 < \delta < 1/2 \) and \( f(1) \geq 1 - \delta + \delta^2 \), then \( f(t) \geq 1 - \delta \) for \( 0\leq t \leq 1 \).

D. Blackwell: “Large excesses for finite-state Markov chains,” pp. 35–39 in System and Bayesian reliability: Essays in honor of Professor Richard E. Barlow on his 70th birthday. Edited by Y. Hayakawa, T. Irony, and M. Xie. Series on Quality, Reliability & Engineering statistics 5. World Scientific (River Edge, NJ), 2001. MR 1896774 incollection

Yu Hayakawa	Related
Min Xie	Related
Telba Irony	Related
Richard E. Barlow	Related

year	title	people

			clear

David H. Blackwell

Markov chains

Filter the Bibliography List