Celebratio Mathematica

[1]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

[2]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.

[3]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

[4]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 \).

[5]D. Blackwell and M. A. Girshick: “On functions of sequences of independent chance vectors with applications to the problem of the ‘random walk’ in \( k \) dimensions,” Ann. Math. Stat. 17 : 3 (September 1946), pp. 310–317. MR 0017898 Zbl 0060.29007 article

Consider a sequence \( \{x_i\} \) of independent chance vectors in \( k \) dimensions with identical distributions, and a sequence of mutually exclusive events \( S_1 \), \( S_2, \dots \), such that \( S_i \) depends only on the first \( i \) vectors and \( \sum P(S_i) = 1 \). Let \( \varphi_i \) be a real or complex function of the first \( i \) vectors in the sequence satisfying conditions:

\( E(\varphi_i) = 0 \) and
\( E(\varphi_j \mid X_1, \dots, X_i) = \varphi_i \) for \( j \geq i \).

Let \( \varphi = \varphi_i \) and \( n = i \) when \( S_i \) occurs. A general theorem is proved which gives the conditions \( \varphi_i \) must satisfy such that \( E\varphi = 0 \). This theorem generalizes some of the important results obtained by Wald for \( k = 1 \). A method is also given for obtaining the distribution of \( \varphi \) and \( n \) in the problem of the ”random walk” in \( k \) dimensions for the case in which the components of the vector take on a finite number of integral values.

[6]D. Blackwell: “On an equation of Wald,” Ann. Math. Stat. 17 : 1 (March 1946), pp. 84–87. MR 0019902 Zbl 0063.00422 article

[7]D. Blackwell: “Conditional expectation and unbiased sequential estimation,” Ann. Math. Stat. 18 : 1 (1947), pp. 105–110. MR 0019903 Zbl 0033.07603 article

It is shown that \[ E\bigl[ f(x) \,E(y \mid x)\bigr] = E(fy) \] whenever \( E(fy) \) is finite, and that \[ \sigma^2 E(y \mid x) \leq \sigma^2 y ,\] where \( E(y \mid x) \) denotes the conditional expectation of \( y \) with respect to \( x \). These results imply that whenever there is a sufficient statistic \( u \) and an unbiased estimate \( t \), not a function of \( u \) only, for a parameter \( \theta \), the function \( E(t \mid u) \), which is a function of \( u \) only, is an unbiased estimate for \( \theta \) with a variance smaller than that of \( t \). A sequential unbiased estimate for a parameter is obtained, such that when the sequential test terminates after \( i \) observations, the estimate is a function of a sufficient statistic for the parameter with respect to these observations. A special case of this estimate is that obtained by Girshick, Mosteller, and Savage [1946] for the parameter of a binomial distribution.

[8]D. Blackwell and M. A. Girshick: “A lower bound for the variance of some unbiased sequential estimates,” Ann. Math. Stat. 18 : 2 (June 1947), pp. 277–280. MR 0020765 Zbl 0032.04401 article

Consider a sequence of independent chance variables \( x_1 \), \( x_2,\dots \) with identical distributions determined by an unknown parameter \( \theta \). We assume that \( Ex_i=\theta \) and that \[ W_k = x_1 + \dots + x_k \] is a sufficient statistic for estimating \( \theta \) from \( x_1,\dots \), \( x_k \). A sequential sampling procedure is defined by a sequence of mutually exclusive events \( S_k \) such that \( S_k \) depends only on \( x_1,\dots \), \( x_k \) and \( \sum P(S_k)=1 \). Define \( W=W_k \) and \( n=k \) when \( S_k \) occurs. In a previous paper by one of the authors [Blackwell 1947] it was shown that if \[ S_k = W_k C(S_1 + \dots + S_{k-1}) ,\] (where \( C(A) \) denotes the event that \( A \) does not occur), the function \[ V(W,n)=E(x_1\mid W,n) \] is an unbiased estimate of \( \theta \), and \[ \sigma^2(V)\leq \sigma^2(x_1) .\] It is the purpose of this note to obtain a lower bound for \( \sigma^2(V) \). Our result is:

\( \displaystyle\sigma^2(V)\geq \frac{\sigma^2(x_1)}{E(n)} \)

[9]D. Blackwell: “A renewal theorem,” Duke Math. J. 15 : 1 (1948), pp. 145–150. MR 0024093 Zbl 0030.20102 article

Let \( x_i \) be independent non-negative chance variables with identical distributions. The asymptotic behavior of the expected number \( U(T) \) of sums \[ s_k = x_1 + \dots +x_k \] lying in the interval \( (0,T) \) has been studied by Feller [1941], using the integral equation of renewal theory and the method of Laplace transforms. Recently Doob [1948] has obtained as a consequence of general theorems on stationary Markov processes the following result: if the distribution of some \( s_k \) is non-singular, then \[ U(T + h) - U(T) \to \frac{h}{E(x_1)} \] as \( T\to\infty \) for every \( h > 0 \). Täcklind [1945] has obtained an excellent estimate for \( U(T) \) itself: when the \( k \)-th moment of \( x_1 \) exists for some \( k > 2 \) and the values of \( x_1 \) are not all integral multiples of some fixed constant, his estimate shows at once that \[ U(T + h) - U(T) \to \frac{h}{E(x_1)} .\]

In this paper we shall prove the following

Unless all values of \( x_1 \) are integral multiples of some fixed constant, \[ U(T + h) - U(T) \to \frac{h}{E(x_1)} \qquad (T\to\infty) \] for every \( h > 0 \). (If \( E(x_1) = \infty \), then \( h/E(x_1) \) is to be interpreted as zero.)

[10]K. J. Arrow, D. Blackwell, and M. A. Girshick: “Bayes and minimax solutions of sequential decision problems,” Econometrica 17 : 3/4 (July–October 1949), pp. 213–244. MR 0032173 Zbl 0034.07504 article

The present paper deals with the general problem of sequential choice among several actions, where at each stage the options available are to stop and take a definite action or to continue sampling for more information. There are costs attached to taking inappropriate action and to sampling. A characterization of the optimum solution is obtained first under very general assumptions as to the distribution of the successive observations and the costs of sampling; then more detailed results are given for the case where the alternative actions are finite in number, the observations are drawn under conditions of random sampling, and the cost depends only on the number of observations. Explicit solutions are given for the case of two actions, random sampling, and linear cost functions.

Kenneth J. Arrow	Related
Meyer Abraham Girshick	Related

[11]R. Bellman and D. Blackwell: “Some two-person games involving bluffing,” Proc. Nat. Acad. Sci. U. S. A. 35 : 10 (October 1949), pp. 600–605. MR 0031700 Zbl 0041.44805 article

[12]D. Blackwell: “On a theorem of Lyapunov,” Ann. Math. Stat. 22 : 1 (March 1951), pp. 112–114. MR 0039033 Zbl 0042.28502 article

[13]D. Blackwell: “On the translation parameter problem for discrete variables,” Ann. Math. Stat. 22 : 3 (September 1951), pp. 393–399. MR 0043418 Zbl 0043.13802 article

For any chance variable \( x = (x_1,\dots \), \( x_N) \) having known distribution, the translation parameter estimation problem is to estimate an unknown constant \( h \), having observed \( y = (x_1+h,\dots \), \( x_N+h) \). Extending the work of Pitman [1939], Girshick and Savage [1951] have, for any loss function depending only on the error of estimate, described an estimate whose risk is a constant \( R \) independent of \( h \), and have shown that under certain hypotheses their estimate is minimax. We investigate whether the Girshick–Savage estimate is admissible, i.e., whether it is impossible to find an estimate with risk \( R(h)\leq R \) for all \( h \) and actual inequality for some \( h \). We consider only bounded discrete variables \( x \), and show that, if all values of \( x \) have all integer coordinates and if the loss \( f(d) \) from an error \( d \) is, for instance, strictly convex and assumes its minimum value, the Girshick–Savage estimate is admissible. Two examples in which the Girshick–Savage estimate is not admissible are given.

[14]R. Bellman and D. Blackwell: “On moment spaces,” Ann. Math. (2) 54 : 2 (September 1951), pp. 272–274. MR 0043866 Zbl 0044.12601 article

[15]D. Blackwell: “Comparison of experiments,” pp. 93–102 in Proceedings of the second Berkeley symposium on mathematical statistics and probability (Berkeley, CA, 31 July–12 August 1950). Edited by J. Neyman. University of California Press (Berkeley and Los Angeles), 1951. MR 0046002 Zbl 0044.14203 inproceedings

Bohnenblust, Shapley, and Sherman [unpublished] have introduced a method of comparing two sampling procedures or experiments; essentially their concept is that one experiment \( \alpha \) is more informative than a second experiment \( \beta \), \( \alpha\supset\beta \), if, for every possible risk function, any risk attainable with \( \beta \) is also attainable with \( \alpha \). If \( \alpha \) is a sufficient statistic for a procedure equivalent to \( \beta \), \( \alpha\succ\beta \), it is shown that \( \alpha\supset\beta \). In the case of dichotomies, the converse is proved. Whether \( \succ \) and \( \supset \) are equivalent in general is not known. Various properties of \( \succ \) and \( \supset \) are obtained, such as the following: if \( \alpha\succ\beta \) and \( \gamma \) is independent of both, then the combination \( (\alpha,\gamma)\succ(\beta,\gamma) \). An application to a problem in \( 2{\times}2 \) tables is discussed.

[16]D. Blackwell: “The range of certain vector integrals,” Proc. Am. Math. Soc. 2 : 3 (September 1951), pp. 390–395. MR 0041195 Zbl 0044.27702 article

[17]D. Blackwell: “On randomization in statistical games with \( k \) terminal actions,” pp. 183–187 in Contributions to the theory of games, vol. II. Edited by H. W. Kuhn and A. W. Tucker. Annals of Mathematics Studies 28. Princeton University Press, 1953. MR 0054923 Zbl 0050.14801 incollection

Harold William Kuhn	Related
Albert William Tucker	Related

[18]D. Blackwell: “Extension of a renewal theorem,” Pacific J. Math. 3 : 2 (1953), pp. 315–320. MR 0054880 Zbl 0052.14104 article

A chance variable \( x \) will be called a \( d \)-lattice variable if

\( \sum_{-\infty}^{\infty}Pr\{x=nd\} = 1 \), and
\( d \) is the largest number for which (1) holds.

If \( x \) is not a \( d \)-lattice variable for any \( d \), \( x \) will be called a nonlattice variable. The main purpose of this paper is to give a proof of:

Let \( x_1 \), \( x_2, \dots \) be independent identically distributed chance variables with \( E(x_1) = m > 0 \) (the case \( m = +\infty \) is not excluded); let \[ S_n = x_1 + \dots + x_n ;\] and, for any \( h > 0 \), let \( U(a,h) \) be the expected number of integers \( n\geq 0 \) for which \( a\leq S_n < a+h \). If the \( x_n \) are nonlattice variables, then \[ U(a,h)\to \frac{h}{m}, 0 \quad\textit{as }a\to +\infty,-\infty .\] If the \( x_n \) are \( d \)-lattice variables, then \[ U(a,d)\to \frac{d}{m}, 0 \quad\textit{as }a\to +\infty,-\infty .\] (If \( m=+\infty \), \( h/m \) and \( d/m \) are interpreted as zero.)

[19]K. J. Arrow, E. W. Barankin, and D. Blackwell: “Admissible points of convex sets,” pp. 87–91 in Contributions to the theory of games, vol. II. Edited by H. W. Kuhn and A. W. Tucker. Annals of Mathematics Studies 28. Princeton University Press, 1953. MR 0054919 Zbl 0050.14203 incollection

A point \( s \) of a closed convex subset \( S \) of \( k \)-space is admissible if there is no \( t\in S \) with \( t_i\leq s_i \) for all \( i=1,\dots \), \( k \), \( t\neq s \). An example is given in which the set \( A \) of admissible points is not closed.

Let \( P \) be the set of vectors \( p=(p_1,\dots \), \( p_k) \) with \( p_i > 0 \) and \( \sum_1^k p_i=1 \), let \( B(p) \) be the set of \( s\in S \) with \[ (p,s)=\min_{t\in S}(p,t) ,\] and let \( B=\sum B(p) \), so that \( B \) consists of exactly those points of \( S \) at which there is a supporting hyperplane whose normal has positive components.

\( B\subset A\subset \overline{B} \). If \( S \) is determined by a finite set, there is a finite set \( p_1,\dots \), \( p_N \), with \( p_j\in P \), such that \( B=\sum_{j=1}^N B(p_j) \), so that, since \( B(p) \) is closed for fixed \( p \), \( B = A = \overline{B} \).

Albert William Tucker	Related
Kenneth J. Arrow	Related
Edward William Barankin	Related
Harold William Kuhn	Related

[20]D. Blackwell: “Equivalent comparisons of experiments,” Ann. Math. Stat. 24 : 2 (1953), pp. 265–272. MR 0056251 Zbl 0050.36004 article

[21]N. M. Smith, Jr., S. S. Walters, F. C. Brooks, and D. H. Blackwell: “The theory of value and the science of decision: A summary,” J. Operations Res. Soc. Amer. 1 : 3 (May 1953), pp. 103–113. MR 0053466 article

Stanley S. Walters	Related
Franklin C. Brooks	Related
Nicholas M. Smith, Jr.	Related

[22]D. Blackwell: “A representation problem,” Proc. Am. Math. Soc. 5 : 2 (1954), pp. 283–287. MR 0061653 Zbl 0055.28804 article

The problem solved in this paper is the following. For a fixed number \( a \), \( 0 < a < 1 \), what functions \( f(x) \) on \( 0 \leq x \leq 1 \) have a representation \begin{equation*}\tag{1} f(x) = \sum_1^{\infty}c_n\varphi_n(x), \end{equation*} where \( c_n\geq 0 \), \( \sum_1^{\infty}c_n \) converges, and each \( \varphi_n \) is the characteristic function of a subset of \( 0\leq x \leq 1 \) of Lebesgue measure \( a \)? Clearly any \( f \) satisfying (1) satisfies \begin{equation*}\tag{2} 0\leq f(x)\leq\frac{1}{a}\int_0^1 f(x)\,dx \quad\text{for all }x, \end{equation*} since \[ f(x)\leq\sum_1^{\infty}c_n=\frac{1}{a}\int_0^1 f(x)\,dx .\] The result of this paper is that (2) is sufficient as well as necessary for a function \( f \) to admit a representation (1).

[23]D. Blackwell and M. A. Girshick: Theory of games and statistical decisions. John Wiley and Sons (New York), 1954. Republished by Dover in 1979. MR 0070134 Zbl 0056.36303 book

[24]D. Blackwell: “On optimal systems,” Ann. Math. Stat. 25 (1954), pp. 394–397. MR 0061776 Zbl 0055.37002 article

For any sequence \( x_1, x_2, \dots \) of chance variables satisfying \( | x_n | \leq 1 \) and \[ E(x_n\mid x_1, \dots, x_{n-1}) \leq -u(\max | x_n| \mid x_1, \dots, x_{n-1}) ,\] where \( u \) is a fixed constant, \( 0 < u < 1 \), and for any positive number \( t \), \[ \mathrm{Pr} \bigl\{ \sup_n (x_1 + \dots + x_n) \geq t\bigr\} \leq \Bigl(\frac{1 - u}{1 + u}\Bigr)^t. \] Equality holds for integral \( t \) when \( x_1 \), \( x_2, \dots \) are independent with \begin{align*} \mathrm{Pr} \{x_n = 1\} &= (1 - u)/2,\\ \mathrm{Pr} \{x_n = -1\} &= (1 + u)/2 . \end{align*} This has a simple interpretation in terms of gambling systems, and yields a new proof of Levy’s extension of the strong law of large numbers to dependent variables, with an improved estimate for the rate of convergence.

[25]D. Blackwell: “On multi-component attrition games,” Naval Res. Logist. Quart. 1 : 3 (1954), pp. 210–216. MR 0068195 article

[26]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.

[27]D. Blackwell and A. H. Bowker: “Meyer Abraham Girshick 1908–1955,” Ann. Math. Stat. 26 : 3 (1955), pp. 365–367. MR 0070573 Zbl 0065.24507 article

Meyer Abraham Girshick	Related
Albert H. Bowker	Related

[28]D. Blackwell: “Controlled random walks,” pp. 336–338 in Proceedings of the International Congress of Mathematicians (Amsterdam, 2 September–9 September 1954), vol. III. Wiskundig Genootschap. E. P. Noordhoff (Groningen), 1956. MR 0085141 Zbl 0073.13204 incollection

[29]D. Blackwell: “On a class of probability spaces,” pp. 1–6 in Proceedings of the third Berkeley symposium on mathematical statistics and probability (Berkeley, CA, 26–31 December 1954 and July–August 1955), vol. II. Edited by J. Neyman. University of California Press (Berkeley and Los Angeles), 1956. MR 0084882 Zbl 0073.12301 inproceedings

[30]D. Blackwell: “An analog of the minimax theorem for vector payoffs,” Pacific J. Math. 6 : 1 (1956), pp. 1–8. MR 0081804 Zbl 0074.34403 article

[31]D. Blackwell: “The entropy of functions of finite-state Markov chains,” pp. 13–20 in Information theory, statistical decision functions, random processes (Liblice, Czech Republic, 28 November–30 November 1956), vol. 1. Edited by J. Kožešnik. Czechoslovak Academy of Sciences (Prague), 1957. MR 0100297 Zbl 0085.12401 incollection

[32]D. Blackwell and J. L. Hodges, Jr.: “Design for the control of selection bias,” Ann. Math. Stat. 28 : 2 (1957), pp. 449–460. MR 0088849 Zbl 0081.36403 article

Suppose an experimenter \( E \) wishes to compare the effectiveness of two treatments, \( A \) and \( B \), on a somewhat vaguely defined population. As individuals arrive, \( E \) decides whether they are in the population, and if he decides that they are, he administers \( A \) or \( B \) and notes the result, until \( nA \)’s and \( nB \)’s have been administered. Plainly, if \( E \) is aware, before deciding whether an individual is in the population, which treatment is to be administered next, he may, not necessarily deliberately, introduce a bias into the experiment. This bias we call selection bias.

We propose to investigate the extent to which a statistician \( S \), by determining the order in which treatments are administered, and not revealing to \( E \) which treatment comes next until after the individual who is to receive it has been selected, can control this selection bias. Thus a design \( d \) is a distribution over the set \( T \) of the \( \binom{2n}{n} \) sequences of length \( 2n \) containing \( nA \)’s and \( nB \)’s.

We shall measure the bias of a design by the maximum expected number of correct guesses which an experimenter can achieve, knowing \( d \), attempting to guess the successive elements of a sequence \( t \in T \) selected by \( d \), and being told after each guess whether or not it is correct. The distribution of the number \( G \) of correct guesses depends both on \( d \) and on the prediction method \( p \) used by the experimenter. We shall consider particularly two designs, the truncated binomial, in which the successive treatments are selected independently with probability \( 1/2 \) each until \( n \) treatments of one kind have occurred, and the sampling design, in which all \( \binom{2n}{n} \) sequences are equally likely.

We shall consider particularly two prediction methods, the convergent prediction, which predicts that treatment which has hitherto occurred less often, and the divergent prediction, which predicts that treatment which has hitherto occurred more often, except that after \( n \) treatments of one kind have been administered, the divergent prediction agrees with the convergent predictions that the other treatment will follow; when both treatments have occurred equally often, either method predicts \( A \) or \( B \) by tossing a fair coin, independently for each case of equality.

We find that among all designs, the truncated binomial minimizes the maximum expected number of correct guesses. For this design, the expected number of correct guesses is independent of the prediction method, and is \[ n + n \binom{2n}{n} \big/ 2^{2n} \sim n + \Bigl(\frac{n}{\pi}\Bigr)^{1/2} .\] With the truncated binomial design, the variance in the number of correct guesses is largest for the divergence strategy and is \[ \frac{3n}{2} - D - \frac{D^2}{4} \sim \frac{(3\pi - 2)n}{2\pi} - 2\Bigl(\frac{n}{\pi}\Bigr)^{1/2}, \] where \( D = n \binom{2n}{n} \big/ 2^{2n - 1} \), and is smallest for the convergence strategy, and is \[ \frac{n}{2} - \frac{D^2}{4} \sim \frac{(\pi - 1)n}{2\pi} .\] For the sampling design, convergent prediction maximizes the expected number of correct guesses; this maximum is \[ n + 2^{2n - 1} \!\big/ \binom{2n}{n} - \frac{1}{2} \sim n + \Bigl(\frac{\pi n}{4}\Bigr)^{1/2}. \] Finally we note that, if treatments are selected independently at random, bias of the kind we discuss disappears, but the treatment numbers can no longer be preassigned. Three such designs are considered: the fixed total design, in which the total number of treatments is a fixed number \( s \), the fixed factor design, in which we continue until \[ \frac{1}{X} + \frac{1}{Y} \leq \frac{2}{n} ,\] where \( X \) is the number of \( A \) treatments and \( Y \) is the number of \( B \) treatments administered, and the fixed minimum design, in which we continue until \( \min (X, Y) = n \). For the fixed total design, we find that, for \( s = 2n + 4 \), \[ \mathrm{Pr}\Bigl(\frac{1}{X} + \frac{1}{Y} \leq \frac{2}{n}\Bigr) \sim 0.955 \] for large \( n \); at the expense of 4 extra observations, we have a bias-free design whose variance factor will with probability \( 0.955 \) be smaller than that in which treatment numbers are preassigned. For the fixed factor design, the additional number of observations required to achieve the given precision has for large \( n \) the distribution of the square of a normal deviate. For the fixed minimum design, in which we guarantee precision for the estimated effect of each treatment, the expected number of additional observations is roughly \( 1.13 (n)^{1/2} \).

[33]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.

[34]D. Blackwell: “On discrete variables whose sum is absolutely continuous,” Ann. Math. Stat. 28 : 2 (1957), pp. 520–521. MR 0088091 Zbl 0078.31602 article

If \( \{Z_n\} \), \( n = 1, 2, \ldots \) is a stationary stochastic process with \( D \) states \[ 0, 1, \dots, D - 1 \quad\text{and}\quad X = \sum^\infty_1 \frac{Z_k}{D^n} ,\] Harris [1955] has shown that the distribution of \( X \) is absolutely continuous if and only if the \( Z_n \) are independent and uniformly distributed over \( {}0 \), \( 1, \dots \), \( D - 1 \), i.e., if and only if the distribution of \( X \) is uniform on the unit interval. In this note we show that if \( \{Z_n\} \), \( n = 1 \), \( 2, \dots \) is any stochastic process with \( D \) states \( {}0 \), \( 1, \dots \), \( D - 1 \) such that \[ X = \sum^\infty_1 \frac{Z_n}{D^n} \] has an absolutely continuous distribution, then the conditional distribution of \[ R_k = \sum^\infty_{n = 1} \frac{Z_{k + n}}{D^n} \] given \( Z_1, \dots \), \( Z_k \) converges to the uniform distribution on the unit interval with probability 1 as \( k \to \infty \). It follows that the unconditional distribution of \( R_k \) converges to the uniform distribution as \( k \to \infty \). Since if \( \{Z_n\} \) is stationary the distribution of \( R_k \) is independent of \( k \), the result of Harris follows.

[35]D. Blackwell, L. Breiman, and A. J. Thomasian: “Proof of Shannon’s transmission theorem for finite-state indecomposable channels,” Ann. Math. Stat. 29 : 4 (1958), pp. 1209–1220. MR 0118570 Zbl 0096.10901 article

Aram John Thomasian	Related
Leo Breiman	Related

[36]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

[37]D. Blackwell and J. L. Hodges, Jr.: “The probability in the extreme tail of a convolution,” Ann. Math. Stat. 30 : 4 (1959), pp. 1113–1120. MR 0112197 Zbl 0099.35105 article

Let \( X_1, X_2, \dots \) be independent and identically distributed random variables with possible values that are integers whose differences have g.c.d. one. Assume the m.g.f. of \( X_1 \) exists in an interval about 0, let \( a \) be any number such that \[ E(X_1) < a < \sup X_1 ,\] and let \[ \varphi(a, t) = E\,e^{t(X_{1-a})} .\] There exists a unique value \( t^{\ast}(a) \) of \( t \) which minimizes \( \varphi(a, t) \) with respect to \( t \); write \[ m(a) = \varphi[ a, t^{\ast}(a)] \quad\text{and}\quad z = e^{-t^{\ast}(a)} .\] Let \( Y_1,Y_2, \dots \) be independent and identically distributed random variables such that \( Y_1 \) and \( X_1 \) have the same range and \[ \Pr(Y_1 = x) = \Pr(X_1 = x) \cdot \frac{e^{t^{\ast}(a)\,(x-a)}}{m(a)} ,\] and let \( \mu_2 = \sigma^2, \mu_3, \mu_4 \) be central moments of \( Y_1 \). We show that \[ \Pr \{X_1 + \dots + X_n = na\} = [ m(a) ]^n \Pr \{Y_1 + \dots + Y_n = na\} ,\] and use this to establish the approximation \[ \Pr \{X_1 + \dots + X_n = na\} = \pi^{\ast\ast}_n[ 1 + 0(n^{-2})] ,\] where \( na \) is a possible value of \( X_1 + \dots + X_n \) and \[ \pi^{\ast\ast}_n = \frac{[ m(a)]^n}{\sigma\sqrt{2\pi n}} \Bigl[ 1 + \frac{1}{8n} \Bigl(\frac{\mu_4}{\mu^2_2} - 3 - \frac{5}{3} \frac{\mu^3_2}{\mu^3_2}\Bigr)\Bigr]. \] Similarly we find that \[ \Pr \{X_1 + \dots + X_n \geq na\} = \Pi^{\ast\ast}_n[ 1 + 0(n^{-2})] ,\] where \[ \Pi^{\ast\ast}_n = \pi^{\ast\ast}_n \cdot \frac{1}{1 - z}\Bigl\{1 - \frac{1}{2n}\Bigl[\frac{(z\mu_3/\mu_2) + z(1 + z)/(1 - z)}{(1 + z)\mu_2}\Bigr]\Bigr\}. \] We provide some numerical illustrations of the accuracy of these approximations, and give a conjectured analog of the leading term of \( \Pi^{\ast\ast}_n \) for nonlattice variables.

[38]D. Blackwell: “Infinite codes for memoryless channels,” Ann. Math. Stat. 30 : 4 (1959), pp. 1242–1244. MR 0127448 Zbl 0104.11701 article

For any finite set \( S \), we denote by \( S^{(N)} \) the set of all sequences \( (s_1, \dots \), \( s_N) \), where \( s_n \in S \) for \( n = 1 \), \( 2, \dots \), \( N \). For a memoryless channel with finite input alphabet \( A \), finite output alphabet \( B \), an infinite code (for transmitting at rate 1) is defined as consisting of

a sequence \( \{f_n\} \) of functions, where \( f_n \) maps \( I^{(n)} \) into \( A \), and \( I \) consists of the two elements 0 and 1,
a nondecreasing sequence \( \{M(n)\} \) of positive integers such that \( M(n)/n \to 1 \) as \( n \to \infty \), and
a sequence \( \{g_n\} \) of functions, where \( \{g_n\} \) maps \( B^{(n)} \) into \( I^{(M(n))} \).

An infinite sequence \( x = (x_1 \), \( x_2, \dots) \) of 0s and 1s, together with an infinite code, defines a sequence of independent output variables \( y_1 \), \( y_2, \dots \), with \[ \Pr \{y_n = b\} = p\bigl(b \mid f_n(x_1, \dots, x_n)\bigr), \] where \( p(b \mid a) \) is the probability that the output symbol of the channel is \( b \), given that the corresponding input symbol is \( a \), and defines a sequence of estimated messages \( t_1 \), \( t_2, \dots \), where \[ t_n = g_n(y_1, \dots\( , \)y_n) .\] We shall say that the code is effective at \( x \) if, with probability 1, \[ t_n = (x_1, \dots,x_{M(n)}) \] for all sufficiently large \( n \), and shall say that the code is effective if it is effective for every \( x \). The result of this note is the

For any memoryless channel with capacity \( C > 1 \), there is an effective code.

[39]D. Blackwell, L. Breiman, and A. J. Thomasian: “The capacity of a class of channels,” Ann. Math. Stat. 30 : 4 (1959), pp. 1229–1241. MR 0127449 Zbl 0104.11604 article

Aram John Thomasian	Related
Leo Breiman	Related

[40]D. Blackwell, L. Breiman, and A. J. Thomasian: “The capacities of certain channel classes under random coding,” Ann. Math. Stat. 31 : 3 (1960), pp. 558–567. MR 0127450 Zbl 0119.13805 article

Aram John Thomasian	Related
Leo Breiman	Related

[41]C. B. Bell, D. Blackwell, and L. Breiman: “On the completeness of order statistics,” Ann. Math. Stat. 31 : 3 (1960), pp. 794–797. MR 0116427 Zbl 0101.12201 article

Let \( X_1, X_2, \dots, X_n \) be a sample of a one-dimensional random variable \( X \); let the order statistic \( T(X_1 \), \( X_2, \dots \), \( X_n) \) be defined in such a manner that \[ T(x_1, x_2, \dots, x_n) = (x^{(1)}, x^{(2)}, \dots, x^{(n)}) \] where \( x^{(1)} \leq x^{(2)} \leq \dots \leq x^{(n)} \) denote the ordered \( x \)’s; and let \( \Omega \) be a class of one-dimensional cpf’s, i.e., cumulative probability functions. The order statistic, \( T \), is said to be a complete statistic with respect to the class \[ \{P^{(n)} \mid P \in \Omega\} \] of \( n \)-fold power probability distributions if \[ E_p^{(n)}\bigl\{h[ T(X_1, \dots, X_n)]\bigr\} = 0 \] for all \( P \in \Omega \) implies \[ h[ T(x_1, \dots, x_n)] = 0 \quad\text{a.e. }P^{(n)} ,\] for all \( F \in \Omega \). The class \( \Omega \) is said to be symmetrically complete whenever the latter condition holds. Since the completeness of the order statistic plays an essential role in nonparametric estimation and hypothesis testing, e.g., Fraser [1954] and Bell [1960], it is of interest to determine those classes of cpf’s for which the order statistic is complete. Many of the traditionally studied classes of cpf’s on the real line are known to be symmetrically complete, e.g., all continuous cpf’s [Lehmann 1959, pp. 131–134, 152–153]; all cpf’s absolutely continuous with respect to Lebesgue measure [Fraser 1957, pp. 23–31]; and all exponentials of a certain form [Lehmann 1959, pp. 131–134]. The object of this note is to present a different [Lehmann 1959, pp. 131–134, 152–153] demonstration of the symmetric completeness of the class of all continuous cpf’s; and to extend this and other known completeness results to probability spaces other than the real line, e.g., Fraser [1954], and Lehmann and Scheffé [1950; 1955].

C. B. Bell	Related
Leo Breiman	Related

[42]D. Blackwell: “Minimax and irreducible matrices,” J. Math. Anal. Appl. 3 : 1 (August 1961), pp. 37–39. MR 0139495 Zbl 0111.33404 article

Call an \( n{\times}n \) matrix \( A = \|A(i,j)\| \) with nonnegative elements irreducible if for every \( i,j \) there is an \( N \) for which \( A^{(N)}(i,j) > 0 \), where \[ A^{(N)} = \|A^{(N)}(i,j)\| \] is the \( N \)-th power of \( A \). A useful result of Frobenius [Karlin 1959] is: Every irreducible \( A \) has a positive eigenvalue \( \lambda_0 \) which is at least as large as the absolute value of any other eigenvalue. This eigenvalue is simple and its eigenvector has all coordinates strictly of the same sign.

We shall obtain this result from the minimax theorem of game theory. Our main result is the

If \( A \) is irreducible, there is exactly one number \( \lambda_0 \) for which the value of the game with matrix \( A - \lambda_0 I \) is zero (\( I \) is the \( n{\times}n \) identity matrix). \( \lambda_0 > 0 \). Each player has a unique good strategy, and all coordinates of each player’s good strategy are positive.

We shall see that this \( \lambda_0 \) is the \( \lambda_0 \) of Frobenius’ result, and that the strategy vectors are the left, right eigenvectors for \( \lambda_0 \).

[43]D. Blackwell: “Exponential error bounds for finite state channels,” pp. 57–63 in Proceedings of the fourth Berkeley symposium on mathematical statistics and probability (Berkeley, CA, 20 June–30 July 1960), vol. I. Edited by J. Neyman. University of California Press (Berkeley and Los Angeles), 1961. MR 0135199 Zbl 0104.11603 incollection

[44]D. Blackwell: “Information theory,” pp. 182–193 in Modern mathematics for the engineer. Edited by E. F. Beckenbach. McGraw-Hill (New York), 1961. MR 0129161 incollection

[45]D. Blackwell: “On the functional equation of dynamic programming,” J. Math. Anal. Appl. 2 : 2 (April 1961), pp. 273–276. MR 0126090 Zbl 0096.35503 article

[46]D. Blackwell and L. Dubins: “Merging of opinions with increasing information,” Ann. Math. Stat. 33 : 3 (1962), pp. 882–886. MR 0149577 Zbl 0109.35704 article

One of us [Blackwell 1957] has shown that if \( Z_n \), \( n = 1 \), \( 2,\dots \) is a stochastic process with \( D \) states, \( {}0 \), \( 1,\dots \), \( D-1 \) such that \[ X=\sum_{n=1}^{\infty} \frac{Z_n}{D^n} \] has an absolutely continuous distribution with respect to Lebesgue measure, then the conditional distribution of \[ R_k = \sum_{n=1}^{\infty} \frac{Z_{k+n}}{D^n} \] given \( Z_1,\dots \), \( Z_k \) converges with probability one as \( k\to\infty \) to the uniform distribution on the unit interval, in the sense that for each \( \lambda \), \( 0 < \lambda \leq 1 \), \[ P(R_k < \lambda\mid Z_1,\dots,Z_k)\to \lambda \] with probability 1 as \( k\to \infty \). It follows that the unconditional distribution of \( R_k \) converges to the uniform distribution as \( k\to\infty \). If \( \{Z_n\} \) is stationary, the distribution of \( R_k \) is independent of \( k \), and hence uniform, a result obtained earlier by Harris [1955]. Earlier work relevant to convergence of opinion can be found in [Savage, 1954, chap. 3, sect. 6].

Here we generalize these results and also show that the conditional distribution of \( R_k \) given \( Z_1,\dots \), \( Z_k \) converges in a much stronger sense. All probabilities in this paper are countably additive.

[47]D. Blackwell: “Discrete dynamic programming,” Ann. Math. Stat. 33 : 2 (1962), pp. 719–726. MR 0149965 Zbl 0133.12906 article

We consider a system with a finite number \( S \) of states \( s \), labeled by the integers \( {}1 \), \( 2, \dots \), \( S \). Periodically, say once a day, we observe the current state of the system, and then choose an action \( a \) from a finite set \( A \) of possible actions. As a joint result of the current state \( s \) and the chosen action \( a \), two things happen:

we receive an immediate income \( i(s,a) \) and
the system moves to a new state \( s^{\prime} \) with the probability of a particular new state \( s^{\prime} \) given by a function \( q = q(s^{\prime}\mid s,a) \).

Finally there is specified a discount factor \( \beta \), \( 0 \leq \beta < 1 \), so that the value of unit income \( n \) days in the future is \( \beta^n \). Our problem is to choose a policy which maximizes our total expected income. This problem, which is an interesting special case of the general dynamic programming problem, has been solved by Howard in his excellent book [Howard 1960]. The case \( \beta = 1 \), also studied by Howard, is substantially more difficult. We shall obtain in this case results slightly beyond those of Howard, though still not complete. Our method, which treats \( \beta = 1 \) as a limiting case of \( \beta < 1 \), seems rather simpler than Howard’s.

[48]D. Blackwell and C. Ryll-Nardzewski: “Non-existence of everywhere proper conditional distributions,” Ann. Math. Stat. 34 : 1 (1963), pp. 223–225. MR 0148097 Zbl 0122.13202 article

[49]D. Blackwell and L. E. Dubins: “A converse to the dominated convergence theorem,” Illinois J. Math. 7 : 3 (1963), pp. 508–514. MR 0151572 Zbl 0146.37503 article

On a probability space \( (\Omega, \mathcal{B}, P) \), let \( \{f_n \), \( n=1 \), \( 2,\dots\} \) be a sequence of nonnegative random variables in \( L_1 \) such that \( f_n \to f\in L_1 \) with probability 1 and define \( g=\sup_n f_n \). If \( g\in L_1 \), the Lebesgue dominated convergence theorem asserts that \( E(f_n)\to E(f) \). More generally, as noted by [Doob 1953, p. 23], if \( g\in L_1 \), then for any Borel field \( \mathcal{B}_0 \) contained in \( \mathcal{B} \), \[ E(f_n\mid\mathcal{B}_0) \to E(f\mid\mathcal{B}_0) \quad\text{a.e.} \] If one extends this result in a minor manner, Lebesgue’s condition \( g\in L_1 \) is not only sufficient but necessary, as the following converse to the dominated convergence theorem asserts.

If \( f_n \geq 0 \), \( f_n \to f \) a.e., \( f_n\in L_1 \), and \( g = \sup_n f_n \notin L_1 \), there are, on a suitable probability space, random variables \( \{f_n^* \), \( n=1 \), \( 2,\dots\} \), \( f^* \), and a Borel field \( \mathcal{C} \) such that \( f^* \), \( f_1^* \), \( f_2^*,\dots \) have the same joint distribution as \( f \), \( f_1 \), \( f_2,\dots \), and \[ P\bigl\{E(f_n^*\mid\mathcal{C})\to E(f^*\mid\mathcal{C})\bigr\} = 0. \]

[50]D. Blackwell and L. E. Dubins: “Sharp bounds on the distribution of the Hardy–Littlewood maximal function,” Proc. Am. Math. Soc. 14 : 3 (1963), pp. 450–453. MR 0148842 Zbl 0118.05401 article

[51]D. Blackwell: “Memoryless strategies in finite-stage dynamic programming,” Ann. Math. Stat. 35 : 3 (1964), pp. 863–865. MR 0162642 Zbl 0127.36406 article

[52]D. Blackwell: “Probability bounds via dynamic programming,” pp. 277–280 in Stochastic processes in mathematical physics and engineering (New York, 30 April–2 May 1963). Edited by R. E. Bellman. Proceedings of Symposia in Applied Mathematics XVI. American Mathematical Society (Providence, RI), 1964. MR 0163347 Zbl 0139.13804 incollection

[53]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

[54]D. Blackwell and D. Freedman: “A remark on the coin tossing game,” Ann. Math. Stat. 35 : 3 (1964), pp. 1345–1347. MR 0169257 Zbl 0129.31502 article

[55]D. Blackwell, P. Deuel, and D. Freedman: “The last return to equilibrium in a coin-tossing game,” Ann. Math. Stat. 35 : 3 (1964), pp. 1344. MR 0169256 Zbl 0129.31501 article

David Freedman	Related
P. Deuel	Related

[56]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.

[57]D. Blackwell: “Discounted dynamic programming,” Ann. Math. Stat. 36 : 1 (1965), pp. 226–235. MR 0173536 Zbl 0133.42805 article

[58]D. Blackwell and L. Dubins: “An elementary proof of an identity of Gould’s,” Bol. Soc. Mat. Mexicana (2) 11 (1966), pp. 108–110. MR 0233713 Zbl 0196.29001 article

[59]P. J. Bickel and D. Blackwell: “A note on Bayes estimates,” Ann. Math. Stat. 38 : 6 (1967), pp. 1907–1911. MR 0219175 Zbl 0155.26103 article

Throughout this paper we are concerned with the problem of estimating a real parameter when the loss function is such that the Bayes estimate exists, is unique, and satisfies a simple Equation, (1.5). If the estimate is unbiased (in the general sense of [Lehmann 1951]) we show under weak conditions that it must satisfy another Equation, (1.14). The main result of Section 1, Theorem 1.3, shows that, in general, these two equations are incompatible unless the Bayes risk is 0. This extends Theorem 11.24 of [Blackwell and Girshick 1954] which states that in estimation with quadratic loss, unbiased Bayes estimates have Bayes risk 0. Some counter-examples at the end of the section indicate the limits of this incompatibility result.

[60]D. Blackwell: “Infinite games and analytic sets,” Proc. Nat. Acad. Sci. U.S.A. 58 : 5 (November 1967), pp. 1836–1837. MR 0221466 Zbl 0224.90077 article

[61]D. Blackwell and J. L. Hodges, Jr.: “Elementary path counts,” Am. Math. Mon. 74 : 7 (August–September 1967), pp. 801–804. Zbl 0155.02903 article

[62]D. Blackwell: “Positive dynamic programming,” pp. 415–418 in Proceedings of the fifth Berkeley symposium on mathematical statististics and probability (Berkeley, CA, 21 June–18 July 1965), vol. I: Theory of statistics. Edited by L. M. Le Cam and J. Neyman. University of California Press (Berkeley and Los Angeles), 1967. MR 0218104 Zbl 0189.19804 incollection

Lucien Marie Le Cam	Related
Jerzy Neyman	Related

[63]D. Blackwell and T. S. Ferguson: “The big match,” Ann. Math. Stat. 39 (1968), pp. 159–163. MR 0223162 Zbl 0164.50305 article

[64]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 \).

[65]D. Blackwell: “A Borel set not containing a graph,” Ann. Math. Stat. 39 : 4 (1968), pp. 1345–1347. MR 0229451 Zbl 0177.48401 article

Examples of Borel sets \( X, Y, B \) such that

\( B \subset X \times Y \),
the projection of \( B \) on \( X \) is \( X \), but
for no Borel-measurable \( d \) mapping \( X \) into \( Y \) is the graph of \( d \) a subset of \( B \),

have been given by [Novikoff 1931; Sierpiński 1931; Addison 1958]. Such examples are of interest in dynamic programming (see for instance [Blackwell 1965]), since if we interpret \( X \) as the set of states of some system, \( Y \) as the set of available acts, and \( I_B(x,y) \) where \( I_B \) is the indicator of \( B \), as your income if the system is in state \( x \) and you choose act \( y \), you can earn 1 in every state, but there is no Borel measurable plan, i.e. function \( d \) from \( X \) into \( Y \), with \( d(x) \) specifying the act to be chosen when the system is in state \( x \), that earns 1 in every state.

This note presents a new example \( X \), \( Y \), \( B \), simpler than those previously given. The proof that it is an example uses ideas from Addison’s construction, and a theorem of Gale and Stewart [1953] on infinite games of perfect information, and is somewhat more complicated than Addison’s

[66]D. Blackwell: “Infinite \( G_{\delta} \)-games with imperfect information,” Zastos. Mat. 10 (1969), pp. 99–101. MR 0243837 Zbl 0232.90068 article

[67]D. Blackwell: Basic statistics. McGraw-Hill (New York), 1969. book

[68]D. Blackwell: “On stationary policies,” J. R. Stat. Soc., Ser. C 133 : 1 (1970), pp. 33–37. With discussion. A Russian translation was published in Mathematika 14:2 (1970). MR 0449711 article

[69]D. Blekuell: “On stationary policies,” Matematika 14 : 2 (1970), pp. 155–159. Russian translation of article in J. R. Stat. Soc., Ser. C 133:1 (1970). Zbl 0224.49019 article

[70]D. Blackwell and D. Freedman: “On the amount of variance needed to escape from a strip,” Ann. Probab. 1 : 5 (1973), pp. 772–787. MR 0356214 Zbl 0293.60041 article

[71]D. Blackwell: “Discreteness of Ferguson selections,” Ann. Statist. 1 : 2 (1973), pp. 356–358. MR 0348905 Zbl 0276.62009 article

[72]D. Blackwell and J. B. MacQueen: “Ferguson distributions via Pólya urn schemes,” Ann. Statist. 1 : 2 (1973), pp. 353–355. MR 0362614 Zbl 0276.62010 article

[73]D. Blackwell, D. Freedman, and M. Orkin: “The optimal reward operator in dynamic programming,” Ann. Probab. 2 : 5 (1974), pp. 926–941. MR 0359818 Zbl 0318.49021 article

David Freedman	Related
Michael Lawrence Orkin	Related

[74]D. Blackwell and L. E. Dubins: “On existence and non-existence of proper, regular, conditional distributions,” Ann. Probab. 3 : 5 (1975), pp. 741–752. MR 0400320 Zbl 0348.60003 article

If \( \mathscr{A} \) is the tail, invariant, or symmetric field for discrete-time processes, or a field of the form \( \mathscr{F}_{t+} \) for continuous-time processes, then no countably additive, regular, conditional distribution given \( \mathscr{A} \) is proper. A notion of normal conditional distributions is given, and there always exist countably additive normal conditional distributions if \( \mathscr{A} \) is a countably generated sub \( \sigma \)-field of a standard space. The study incidentally shows that the Borel-measurable axiom of choice is false. Classically interesting subfields \( \mathscr{A} \) of \( \mathscr{B} \) possess certain desirable properties which are the defining properties for \( \mathscr{A} \) to be “regular” in \( \mathscr{B} \).

[75]D. Blackwell: “The stochastic processes of Borel gambling and dynamic programming,” Ann. Statist. 4 : 2 (1976), pp. 370–374. MR 0405557 Zbl 0331.93055 article

[76]D. Blackwell: “Borel-programmable functions,” Ann. Probab. 6 : 2 (1978), pp. 321–324. MR 0460573 Zbl 0398.28002 article

[77]D. Blackwell and M. A. Girshick: Theory of games and statistical decisions, reprint edition. Dover Books on Advanced Mathematics. Dover Publications (New York), 1979. Republication of 1954 original. MR 597146 Zbl 0439.62008 book

[78]D. Blackwell: “There are no Borel SPLIFs,” Ann. Probab. 8 : 6 (1980), pp. 1189–1190. MR 602393 Zbl 0451.28001 article

[79]D. Blackwell: “Borel sets via games,” Ann. Probab. 9 : 2 (1981), pp. 321–322. MR 606995 Zbl 0455.28002 article

[80]D. Blackwell and R. V. Ramamoorthi: “A Bayes but not classically sufficient statistic,” Ann. Statist. 10 : 3 (1982), pp. 1025–1026. MR 663456 Zbl 0485.62004 article

[81]D. Blackwell and L. E. Dubins: “An extension of Skorohod’s almost sure representation theorem,” Proc. Am. Math. Soc. 89 : 4 (1983), pp. 691–692. MR 718998 Zbl 0542.60005 article

[82]D. Blackwell: “A hypothesis-testing game without a value,” pp. 79–82 in A Festschrift for Erich L. Lehmann. Edited by P. J. Bickel, K. A. Doksum, and J. L. Hodges. Wadsworth Statistics/Probability Series. Wadsworth (Belmont, CA), 1983. MR 689739 Zbl 0525.62006 incollection

Kjell Andreas Doksum	Related
Joseph Lawson Hodges, Jr.	Related
Erich Leo Lehmann	Related
Peter J. Bickel	Related

[83]D. Blackwell and A. Maitra: “Factorization of probability measures and absolutely measurable sets,” Proc. Am. Math. Soc. 92 : 2 (1984), pp. 251–254. MR 754713 Zbl 0554.60001 article

[84]D. Blackwell: Approximate normality of large products. Preprint 54, U.C. Berkeley Statistics Department (Berkeley, CA), 1985. techreport

[85]“David Harold Blackwell,” pp. 18–32 in Mathematical people: Profiles and interviews. Edited by D. J. Albers and G. L. Alexanderson. AK Peters/CRC Press (Boston), 1985. Interview by Donald J. Albers. incollection

Donald J. Albers	Related
Gerald Lee Alexanderson	Related

[86]D. Blackwell and R. D. Mauldin: “Ulam’s redistribution of energy problem: Collision transformations,” pp. 149–153 in In memory of Stan Ulam, published as Lett. Math. Phys. 10 : 2–3 (1985). MR 815237 Zbl 0582.60035 incollection

Stanisław Marcin Ulam	Related
Richard Daniel Mauldin	Related

[87]M. H. DeGroot: “A conversation with David Blackwell,” Statist. Sci. 1 : 1 (1986), pp. 40–53. MR 833274 Zbl 0597.01014 article

[88]D. Blackwell and S. Ramakrishnan: “Stationary plans need not be uniformly adequate for leavable, Borel gambling problems,” Proc. Am. Math. Soc. 102 : 4 (1988), pp. 1024–1027. MR 934886 Zbl 0658.60072 article

[89]D. Blackwell: “Operator solution of infinite \( G_\delta \) games of imperfect information,” pp. 83–87 in Probability, statistics, and mathematics: Papers in honor of Samuel Karlin. Edited by T. W. Anderson, K. B. Athreya, and D. L. Iglehart. Academic Press (Boston, MA), 1989. MR 1031279 Zbl 0696.90094 incollection

Theodore W. Anderson	Related
Donald L. Iglehart	Related
Samuel Karlin	Related
Krishna B. Athreya	Related

[90]M. Proschan: “A note on D. H. Blackwell and J. L. Hodges, Jr.: ‘Design for the control of selection bias’, and P. Diaconis and R. L. Graham: ‘The analysis of sequential experiments with feedback to subjects’,” Ann. Statist. 19 : 2 (1991), pp. 1106–1108. The paper of Diaconis and Graham is Ann. Statist. 9:1 (1981) pp. 3–23. Commentary on Ann. Math. Stat. 28:2 (1957). MR 1105868 Zbl 0747.62021 article

Ronald Lewis Graham	Related
Joseph Lawson Hodges, Jr.	Related
Michael Proschan	Related
Persi Diaconis	Related

[91]D. Blackwell: “Minimax vs. Bayes prediction,” Probab. Engrg. Inform. Sci. 9 : 1 (1995), pp. 53–58. Available open access here. MR 1336801 article

[92]D. Blackwell: “Games with infinitely many moves and slightly imperfect information,” pp. 407–408 in Games of no chance (MSRI, Berkeley, CA 11–21 July 1994). Edited by R. J. Nowakowski. MSRI Publications 29. Cambridge University Press, 1996. Zbl 0873.90115 incollection

[93]D. Blackwell and P. Diaconis: “A non-measurable tail set,” pp. 1–5 in Statistics, probability and game theory: Papers in honor of David Blackwell. Edited by T. S. Ferguson, L. S. Shapley, and J. B. MacQueen. IMS Lecture Notes–Monograph Series 30. Institute of Mathematical Statistics (Hayward, CA), 1996. MR 1481768 incollection

Lloyd Stowell Shapley	Related
Thomas S. Ferguson	Related
James B. MacQueen	Related
Persi Diaconis	Related

[94]T. S. Ferguson, L. S. Shapley, and J. B. MacQueen: “Preface [Biography of David Blackwell],” pp. v–xiv in Statistics, probability and game theory: Papers in honor of David Blackwell. Edited by T. S. Ferguson, L. S. Shapley, and J. B. MacQueen. IMS Lecture Notes–Monograph Series 30. Institute of Mathematical Statistics (Hayward, CA), 1996. MR 1481767 incollection

This volume has been created to honor Professor David Blackwell of the University of California at Berkeley by his students, colleagues, friends and admirers. Most of the papers of this volume are on topics connected with areas in which Blackwell has played a major role. There are review articles on Comparison of Experiments, on Games of Timing, on Merging of Opinions, on Associate Memory Models, and SPLIFs etc. There are historical views of Carnap, of von Mises, and of the Berkeley Statistics Department. But the bulk of the articles are research articles in Probability, Statistics, Gambling, Game Theory, Markov Decision Processes, Set Theory and Logic. Special care has been taken to achieve a wide variety of readable and interesting papers from outstanding scholars.

We present a brief biography of Blackwell, followed by a short review of his research accomplishments. We also include a bibliography of his publications, which, as may be seen from the first article of this volume, becomes out of date with the publication of this volume

Lloyd Stowell Shapley	Related
Thomas S. Ferguson	Related
James B. MacQueen	Related

[95]Statistics, probability and game theory: Papers in honor of David Blackwell. Edited by T. S. Ferguson, L. S. Shapley, and J. B. MacQueen. IMS Lecture Notes–Monograph Series 30. Institute of Mathematical Statistics (Hayward, CA), 1996. MR 1481766 Zbl 0996.60500 book

Lloyd Stowell Shapley	Related
Thomas S. Ferguson	Related
James B. MacQueen	Related

[96]K. W. Wachter, D. Blackwell, and E. A. Hammel: “Testing the validity of kinship microsimulation,” Math. Comput. Modelling 26 : 6 (1997), pp. 89–104. Zbl 0884.92034 article

Computer microsimulation is capable of generating detailed reconstructions and forecasts of the numbers of living kin that members of a population have. The available detail, specificity, and consistency of vital rates for the past and the accuracy of vital rates projected for the future necessarily limit the accuracy of the kinship estimates that can be produced.

This study is an external validity test of Reeves’ 1982 reconstruction and forecast of U.S. kin counts with the SOCSIM microsimulation program [Reeves 1982]. The external standard is provided by estimates from the 1987-1988 wave of the National Survey of Families and Households, the first detailed information on numbers and ages of kin for the United States. We compare forecasts with estimates for average numbers of living grandchildren, living full-siblings, and living half-siblings as functions of age.

We find remarkably close agreement for some of the predictions, along with several instances of systematic discrepancies. The discrepancies most likely stem from errors in the forecasts rather than in the survey estimates. Interacting rather than isolable errors appear to be responsible. Our validity tests provide a basis for qualified faith in the effectiveness of kinship microsimulation.

E. A. Hammel	Related
Kenneth Willcox Wachter	Related

[97]D. Blackwell: “Large deviations for martingales,” pp. 89–91 in Festschrift for Lucien Le Cam. Edited by D. Pollard, E. N. Torgersen, and G. L. Yang. Springer (New York), 1997. MR 1462940 Zbl 0883.60041 incollection

Erik Nikolai Torgersen	Related
Grace Lo Yang	Related
David Pollard	Related
Lucien Marie Le Cam	Related

[98]Learning in games: A symposium in honor of David Blackwell, published as Games Econom. Behav. 29 : 1/2. Issue edited by D. P. Foster, D. K. Levine, and R. V. Vohra. Elsevier (San Diego, CA), 1999. MR 1729307 Zbl 1131.91300 book

Rakesh Vinay Vohra	Related
David K. Levine	Related
Dean P. Foster	Related

[99]D. Blackwell: “The square-root game,” pp. 35–37 in Game theory, optimal stopping, probability and statistics: Papers in honor of Thomas S. Ferguson. Edited by F. T. Bruss and L. Le Cam. IMS Lecture Notes–Monograph Series 35. Institute of Mathematical Statististis (Beachwood, OH), 2000. MR 1833849 Zbl 0988.91004 incollection

Thomas S. Ferguson	Related
Franz Thomas Bruss	Related
Lucien Marie Le Cam	Related

[100]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

[101]D. Blackwell: “The prediction of sequences,” Internat. J. Game Theory 31 : 2 (2002), pp. 245–251. Special anniversary issue. MR 1968990 Zbl 1082.91036 article

[102]N. Agwu, L. Smith, and A. Barry: “Dr. David Harold Blackwell, African American pioneer,” Math. Mag. 76 : 1 (2003), pp. 3–14. MR 2084114 article

Aissatou Barry	Related
Luella Smith	Related
Nkechi Agwu	Related

[103]M. Bhattacharjee, R. Lockhart, J. Rolph, G. Roussas, H. Tucker, R. J.-B. Wets, P. Bickel, T. S. Ferguson, A. Lo, M. L. Puri, S. Stigler, W. Sudderth, Y. Yatracos, D. Brillinger, L. A. Goodman, J. Shaffer, H. Chernoff, P. Diaconis, M. Rosenblatt, and F. J. Samaniego: “A tribute to David Blackwell.” Edited by G. G. Roussas. Notices Am. Math. Soc. 58 : 7 (2011), pp. 912–928. MR 2850553 Zbl 1225.01082 article

Thomas S. Ferguson	Related
Leo A. Goodman	Related
Albert Yee-Lap Lo	Related
George Gregory Roussas	Related
Roger J-B Wets	Related
Madan Lal Puri	Related
Murray Rosenblatt	Related	Volume
Francisco J. Samaniego	Related
Juliet Popper Shaffer	Related
John Rolph	Related
Manish C. Bhattacharjee	Related
Stephen Mack Stigler	Related
William D. Sudderth	Related
Yannis Yatracos	Related
Richard Lockhart	Related
Howard Tucker	Related
Peter J. Bickel	Related
David Brillinger	Related
Herman Chernoff	Related
Persi Diaconis	Related

@article {key2850553m,
	AUTHOR = {Bhattacharjee, Manish and Lockhart,
		 Richard and Rolph, John and Roussas,
		 George and Tucker, Howard and Wets,
		 Roger J.-B. and Bickel, Peter and Ferguson,
		 Thomas S. and Lo, Albert and Puri, Madan
		 L. and Stigler, Stephen and Sudderth,
		 W. and Yatracos, Yannis and Brillinger,
		 David and Goodman, Leo A. and Shaffer,
		 Juliet and Chernoff, Herman and Diaconis,
		 Persi and Rosenblatt, Murray and Samaniego,
		 Francisco J.},
	TITLE = {A tribute to {D}avid {B}lackwell},
	JOURNAL = {Notices Am. Math. Soc.},
	FJOURNAL = {Notices of the American Mathematical
		 Society},
	VOLUME = {58},
	NUMBER = {7},
	YEAR = {2011},
	PAGES = {912--928},
	URL = {http://www.ams.org/notices/201107/rtx110700912p.pdf},
	NOTE = {Edited by G. G. Roussas.
		 MR:2850553. Zbl:1225.01082.},
	ISSN = {0002-9920},
	CODEN = {AMNOAN},
}

[104]R. Swift: “Obituary: David Blackwell,” Math. Sci. 36 : 1 (2011), pp. 70–71. MR 2829586 Zbl 1228.01049 article

David H. Blackwell

Complete Bibliography