Search

A recent theorem of Orey [12] (see also [1], [6], [7], [13]) asserts that if $T$ is an $L_1$ operator induced on a discrete measure space by an irreducible recurrent aperiodic Markov matrix, then the condition (C) holds: $f \epsilon L_1, \int f = 0$ implies that $T^n f$ converges to zero in $L_1$. In an attempt to determine when (C) holds for more general operators, we at first prove the following (Theorem 1.1): Let $T$ be a positive linear contraction operator on $L_1$; if $T^nf$ and $T^{n+1}f$ intersect slightly, but uniformly in $f$ in the unit sphere of $L_1$, then $T^nf - T^{n+1}f$ converges to zero in norm. (C) follows if $T$ is conservative and ergodic (Corollary 1.3). In Section 2 we derive from this a simple proof of Orey's theorem. The main result of the paper is in Section 3 and could be called a "zero-two" theorem: Let $P(x, A)$ be a Markov kernel, and assume that there is a $\sigma$-finite measure $m$ such that for each $A, m(A) = 0$ implies $P(x, A) = 0$ a.e. and $m(A) > 0$ implies $\sum^\infty_{n=0} P^{(n)}(x, A) = \infty$ a.e. Then the total variation of the measure $P^{(n)}(x, \cdot) - P^{(n+1)}(x, \cdot)$ is either a.e. 2 for all $n$ or it converges a.e. to 0 as $n \rightarrow \infty$. In Section 4 it is shown that a version of the zero-two theorem essentially contains the Jamison-Orey generalization of Orey's theorem to Harris processes. Section 1 and Section 2 of this paper do not assume any knowledge of either operator ergodic theory or probability. Some known results in ergodic theory are applied in Section 3, but the proof of the main theorem does not depend on them.

Let $J$ be a finite non-empty set and let $S(J)$ denote the set of all finite sequences of elements of $J$. If $s = (\delta_1, \cdots, \delta_m)\in S(J)$ and $t = (\mu_1, \cdots, \mu_n)\in S(J)$, then $st$ will denote the combined sequence $(\delta_1, \cdots, \delta_m, \mu_1, \cdots, \mu_n)$. The singleton sequence $(\delta)$ will be denoted by $\delta$. The symbol $s^2$ will mean the sequence $ss$ and the symbols $s^3,s^4$, etc., are defined similarly. Suppose $\{Y_n\}$ is a stationary process with state-space $J$. If $s \in S(J)$ and has length $n, p(s)$ denotes $P\lbrack (Y_1, \cdots, Y_n) = s \rbrack$. The rank $n(\delta)$ of a $\delta \in J$ is defined to be the largest integer $n$ such that we can find $2n$ sequences $s_1, \cdots, s_n, t_1, \cdots, t_n$ in $S(J)$ such that the $n \times n$ matrix $\|p(s_i\delta t_j)\|$ is non-singular. Suppose now that $\{Y_n\}$ is a function of a finite Markov chain (hereafter abbreviated ffMc). That is, let there exist a stationary Markov chain $\{X_n\}$ with a finite state-space $I$ and a function $f$ on $I$ onto $J$ such that $\{Y_n\}$ and $\{f(X_n)\}$ have the same distribution. Then Gilbert [5] has shown that $n(\delta) \leqq N(\delta)$ for all $\delta \in J$, where $N(\delta)$ is the number of elements in $f^{-1}\lbrack\{\delta\}\rbrack$. If we can find $\{X_n\}$ and $f$ in such a way that $n(\delta) = N(\delta)$ for all $\delta \in J$, then $\{Y_n\}$ is said to be a regular ffMc. The motivation for investigating the regularity property of a ffMc has been made clear by Gilbert in the first and the last paragraphs of Section 2 of [5]. Fox and Rubin [3] have given an example of a process $\{Y_n\}$ which has $n(\delta) < \infty$ for all $\delta \in J$ but which is not a ffMc. In the first part of this paper we expand their example into a class of examples and show that some of these examples yield nonregular ffMc. These examples are of a different nature than those given in [1], Section 4. Further our method of investigation is different from that employed by Fox and Rubin. The second part of this paper is devoted to proving that an exchangeable process which is a ffMc is a regular ffMc.

A vector variable $\mathbf{X}$ is said to have a linear structure if it can be written as $\mathbf{X} = \mathbf{AY}$ where $\mathbf{A}$ is a matrix and $\mathbf{Y}$ is a vector of independent random variables called structural variables. In earlier papers the conditions under which a vector random variable admits different structural representations have been studied. It is shown, among other results, that complete non-uniqueness, in some sense, of the linear structure characterizes a multivariate normal variable. In the present paper we prove a general decomposition theorem which states that any vector variable $\mathbf{X}$ with a linear structure can be expressed as the sum $(\mathbf{X}_1 + \mathbf{X}_2)$ of two independent vector variables $\mathbf{X}_1, \mathbf{X}_2$ of which $\mathbf{X}_1$ is non-normal and has a unique linear structure, and $\mathbf{X}_2$ is multivariate normal variable with a nonunique linear structure.

Let $(\mathscr{X}, \mathscr{a})$ be a measurable space and $\Theta$ be an open subset of a $k$-dimensional Euclidean space. For each $\theta \varepsilon \Theta$ let $P_\theta$ be a probability measure on $\mathscr{a}$. We assume that for every $\theta \varepsilon \Theta, \{X_n, n \geqq 0\}$ is a Markov process defined on $(\mathscr{X}, \mathscr{a})$ into $(R, \mathscr{B})$, where $(R, \mathscr{B})$ denotes the Borel real line. Furthermore, we denote by $\mathscr{a}_n$ the $\sigma$-fields induced by the random variables $\{X_0, X_1, \cdots, X_n\}$, and by $P_{n, \theta}$ the restriction of $P_\theta$ to $\mathscr{a}_n$. In the present paper we give conditions under which the sequence of families of probability measures $\{P_{n,\theta}, \theta \varepsilon \Theta\}$ has the desirable property of being differentially asymptotically normal. This implies that in some neighborhood of $\theta \varepsilon \Theta, \{P_{n,\theta}, \theta \varepsilon \Theta\}, n \geqq 0$ can be, for certain problems, approximately treated as if they were normal. For a detailed account of the notions involved in this paper the reader is referred to [5], in particular, Section 5. Also in the Appendix of the present paper one can find the definitions of the concepts most frequently used in this work, including that of the differentially asymptotically normal families of distributions. In Section 2 the required notation is introduced and also the assumptions being made throughout the paper are listed. In Section 3 we state the main result, and in the following subsections we give the proof of it in several steps.

Let $\{Z(t); t \geqq 0\}$ be a one dimensional age dependent branching process with offspring probability generating function (pgf) $h(s) \equiv \sum^\infty_{j=0} p_js^j$ and lifetime distribution function $G(t)$ (see Section 2 for definitions). If $m(t) \equiv EZ(t)$ is the mean function let $Y(t) = Z(t)/m(t)$. Our objective in this paper is to study the limiting behavior of the process $\{Y(t); t \geqq 0\}$. The main result is THEOREM 0. Assume $Z(0) \equiv 1, m = h'(1) > 1, G(0+) = 0$. (Here $\rightarrow_p$ and $\rightarrow_d$ mean convergence in probability and distribution respectively). Then: \begin{equation*}\tag{1}\sum^\infty_{j=2} j \log jp_j = \infty\quad\text{implies} Z(t)/EZ(t) \rightarrow_p 0\end{equation*} and \begin{equation*}\tag{2}\sum^\infty_{j=2} j \log jp_j < \infty\quad\text{implies} Z(t)/EZ(t) \rightarrow_d W\end{equation*} where $W$ is an nonnegative random variable such that (a) $EW = 1$, (b) $\varphi(u) = E(e^{-uW})$ for $u \geqq 0$ satisfies \begin{equation*}\tag{3}\varphi(u) = \int^\infty_0 h(\varphi(ue^{-\alpha y})) dG(y)\end{equation*} where $\alpha$ is the unique root of the equation $m \int^\infty_0 e^{-\alpha y} dG(y) = 1$ (c) $P(W = 0) = q$ the extinction probability (d) $W$ has an absolutely continuous distribution on the positive real axis and the density function is continuous. That is, there exists a nonnegative continuous function $g(x)$ defined for $x > 0$ such that for $0 < x_1 < x_2 < \infty$ \begin{equation*}\tag{4}P(x_1 < W < x_2) = \int^{x_2}_{x_1} g(x) dx.\end{equation*} Kesten and Stigum [4] proved the above result for the case when $G(x)$ is the step function \begin{equation*}\tag{5}\begin{align*}G(x) = 0 \text{if} x\leqq 1 \\ = 1\quad x > 1.\end{align*}\end{equation*} This is the Galton-Watson process in discrete time. They considered the multi-dimensional case. Athreya and Karlin [1] considered the case (here $0 < \lambda < \infty)$ \begin{equation*}\tag{6}\begin{align*}G(x) = 1 - e^{-\lambda x} \text{for} x > 0 \\ = 0\quad x \leqq 0.\end{align*}\end{equation*} This is the continuous time Markov branching process. Their approach was via split times. Levinson [6] established the law convergence of $Z(t)/EZ(t)$ under conditions slightly stronger than ours. Harris [3] claimed mean square convergence of $Z(t)/EZ(t)$ when $h'' (1) < \infty$ and the absolute continuity of $W$ when in addition to $h'' (1) < \infty, 1 - G(t) = O(e^{-cr})$ for some $c > 0$. Our result is the sharpest known in this direction in as much as (i) we establish the convergence of $Z(t)/EZ(t)$ without any conditions, (ii) we give a necessary and sufficient condition for the nondegeneracy of the limit random variable $W$ and (iii) when $W$ is nondegenerate we establish the absolute continuity without any extra assumptions. The methods employed in this paper are all extremely simple. Among them are a simplified and sharpened form of Levinson's [6] arguments and a simplification of Stigum's [7] idea to prove absolute continuity of $W$. One of the important ideas used here is the exploitation of the underlying Galton-Watson process constituted by the size $\{\zeta_n\}$ of the different generations. The key to the understanding of the moment condition $\sum_j j \log jp_j < \infty$ is the simple Lemma 1. Here is an outline of the rest of the paper. In Section 2 we describe the setting and introduce the necessary terminology and notation. The functional equation (3) is studied in detail in Section 3 where it is shown that a necessary and sufficient condition for (3) to have a nontrivial solution is the finiteness of $\sum j \log jp_j$. The next section explores the connection between the process $\{Z(t); t \geqq 0\}$ and the underlying Galton-Watson process $\{\zeta_n; n = 0, 1, 2, \cdots\}$ and shows that if $\sum j \log jp_j = \infty$ then $Z(t)/EZ(t) \rightarrow_p 0$. Assuming $\sum j \log jp_j < \infty$ the convergence in distribution of $Z(t)/EZ(t)$ to a nondegenerate random variable $W$ is shown in Section 5 while Section 6 takes up the proof of absolute continuity. The last section lists some open problems.

Associated with certain of the learning models introduced by Bush and Mosteller [1] are random walks $p_1, p_2, p_3, \cdots$ on the closed unit interval with transition probabilities of the form \begin{equation*}\tag{1}P\lbrack p_{n + 1} = p_n + \theta_1(1 - p_n) \mid p_n\rbrack = \varphi(p_n)\end{equation*} and \begin{equation*}\tag{2}P\lbrack p_{n + 1} = p_n - \theta_2p_n \mid p_n\rbrack = 1 - \varphi(p_n)\end{equation*} where $0 < \theta_1, \theta_2 < 1$ and $\varphi$ is a mapping of the closed unit interval into itself. In the experiments to which these models are applied, response alternatives $A_1$ and $A_2$ are available to a subject on each of a sequence of trials, and $p_n$ is the probability that the subject will make response $A_1$ on trial $n$. Depending on which response is actually made, one of two events $E_1$ or $E_2$ ensues. These events are associated, respectively, with the increment $p_n \rightarrow p_n + \theta_1(1 - p_n)$ and the decrement $p_n \rightarrow p_n - \theta_2p_n$ in $A_1$ response probability. The conditional probabilities $\pi_{ij}$ of event $E_j$ given response $A_i$ do not depend on the trial number $n$. Thus (1) and (2) are obtained with $\varphi(p) = \pi_{11}p + \pi_{21}(1 - p)$. Since the linearity of the functions $\varphi$ which arise in this way is of no consequence for the work presented in this paper, we will assume instead simply that \begin{equation*}\tag{3}\varphi \varepsilon C^2(\lbrack 0, 1\rbrack).\end{equation*} We impose one further restriction on $\varphi$ which excludes some cases of interest in learning theory: \begin{equation*}\tag{4}\epsilon_1 = \min_{0 \leqq p \leqq 1} \varphi(p) > 0 \text{and} \epsilon_2 = \max_{0 \leqq p \leqq 1} \varphi(p) < 1.\end{equation*} It follows from a theorem of Karlin ([5], Theorem 37) that under (1)-(4) the distribution function $F^{(n)}_{\theta_1,\theta_2,\varphi}$ of $p_n$ (which depends, of course, on the distribution $F$ of $p_1$) converges as $n$ approaches infinity to a distribution $F_{\theta_1,\theta_2,\varphi}$ which does not depend on $F$. It is with the distributions $F_{\theta_1,\theta_2,\varphi}$ that the present paper is concerned. Very little is known about distributions of this family, though some results may be found in Karlin [5], Bush and Mosteller [1], Kemeny and Snell [6], Estes and Suppes [3], and McGregor and Hui [8]. The only theorem in the literature directly relevant to the present work is one of McGregor and Zidek [9] as a consequence of which, in the case $\theta_1 = \theta_2 = \theta, \varphi(p) \equiv \frac{1}{2}$, $\lim_{\theta \rightarrow 0} \lim_{n \rightarrow \infty} P\lbrack\theta^{-\frac{1}{2}}(p_n - \frac{1}{2}) \leqq x\rbrack = \Phi(8^{\frac{1}{2}}x)$ where $\Phi$ denotes the standard normal distribution function; that is, the distribution $F_{\theta,\theta,\frac{1}{2}}(\theta^{\frac{1}{2}}x + \frac{1}{2})$ converges to a normal distribution as the "learning rate" parameter $\theta$ tends to 0. We will prove, by means of another method, that this phenomenon is of much greater generality. Theorem 1 below shows that, for any positive constant $\zeta$ and any $\varphi$ with $\max_{0 \leqq p \leqq 1}\varphi'(p) < \min (1, \zeta)/\max (1, \zeta)$ there is a constant $\rho$ such that $F_{\theta,\zeta\theta,\varphi}(\theta^{\frac{1}{2}}x + \rho)$ converges to a normal distribution as $\theta \rightarrow 0$. A nonnormal limit is obtained if $\theta_1$ approaches 0 while $\theta_2$ remains fixed as is shown in Theorem 2. In this case $F_{\theta_1,\theta_2,\varphi}(\theta_1x)$ converges to an infinite convolution of geometric distributions. If $f(p,\theta) = p + \theta(1 - p)$ then (1) and (2) can be written in the form \begin{equation*}\tag{5}P\lbrack p_{n + 1} = f(p_n, \theta_1) \mid p_n\rbrack = \varphi(p_n)\end{equation*} and \begin{equation*}\tag{6}P\lbrack p_{n + 1} = 1 - f(1 - p_n, \theta_2) \mid p_n\rbrack = 1 - \varphi(p_n).\end{equation*} In Section 4 it is shown that the linearity of $f(p,\theta)$ in $p$ and $\theta$ is not essential to the phenomena discussed above. Theorems 3 and 4 present generalizations of Theorems 2 and 1, respectively, to "learning functions" $f(p,\theta)$ subject only to certain fairly weak axioms. A somewhat different learning model, Estes [2] $N$-element pattern model, leads to a finite Markov chain $p_1, p_2, p_3, \cdots$ with state space $S_N = \{jN^{-1}: j = 0, 1, \cdots, N\}$ and transition probabilities \begin{align*}\tag{7}P\lbrack p_{n + 1} &= p_n + N^{-1} \mid p_n\rbrack = \varphi(p_n), \\ \tag{8}P\lbrack p_{n + 1} &= p_n - N^{-1} \mid p_n\rbrack = \psi(p_n),\\ \end{align*} and \begin{equation*}\tag{9}P\lbrack p_{n + 1} = p_n \mid p_n\rbrack = 1 - \varphi(p_n) - \psi(p_n)\end{equation*} where $\varphi(p) = c\pi_{21}(1 - p), \psi(p) = c\pi_{12}p, 0 < c \leqq 1$, and for the sake of this discussion we suppose that $0 < \pi_{12}, \pi_{21} < 1$. In this case a limiting distribution $F_{N, \varphi,\psi}$ of $p_n$ as $n \rightarrow \infty$ exists and is independent of the distribution of $p_1$ by a standard theorem on Markov chains. Estes [2] showed that the limit is binomial over $S_N$ with mean $r = \pi_{21}/(\pi_{12} + \pi_{21})$. It then follows from the central limit theorem that $\lim_{N \rightarrow \infty}\lim_{n \rightarrow \infty} P\lbrack N^{\frac{1}{2}}(p_n - r) \leqq x\rbrack = \Phi\lbrack x/(r(1 - r))^{\frac{1}{2}}\rbrack.$ In Section 5 it is shown that our method permits an extension of this result to much more general $\varphi$ and $\psi$.

In this paper we have studied certain combinatorial properties of incomplete block designs and efficient necessary conditions for the existence of affine resolvable balanced incomplete block (b.i.b., for abbreviation) designs. Two theorems give combinatorial properties of certain b.i.b. designs. The well known inequality of Fisher between the number of varieties and number of blocks is shown in this paper to hold under very general conditions. An intrinsic characteristic property of symmetrical b.i.b. designs is given in another theorem. In the last two theorems we have deduced efficient necessary conditions for the existence of affine resolvable b.i.b. designs. Besides these there are some minor results. Utilizing the simple yet very fruitful idea of associating an incidence matrix with a design, all the results are deduced with the help of arguments of algebra of matrices and linear equations. The last theorem requires the use of the celebrated four square theorem of Lagrange and a result due to Legendre in number theory.

This paper continues the study started in [13] where classes of operations were investigated in the partially ordered vector space approach to the theory of statistical physical systems. In this approach the set of states is represented by a norm closed generating coneK in a complete base norm space (V, K, B) and the set of operations is represented by the setP of positive norm non-increasing linear operators onV. In actual physical experiments it is usually the case that only certain subsets ofK are available and it is supposed that the set Γ(K) of such subsets is the set of split faces ofK. The properties of two important classes of operation are examined. The first classP of strong operations has the property that each member leaves every element of Γ(K) invariant and therefore can be measured in every restricted situation. The second classPP of pure operations has the property above and also sends pure states into pure states. A study is made, in terms of the structure of Γ(K), of when such operations are physically relevant. The paper ends with an examination of Γ(K),P, PP in the Von Neumann algebra model.

A factorial experiment involving $m$ factors such that the $i$th factor has $m_i$ levels is termed an asymmetrical factorial design. If the number of levels is equal to one another the experiment is termed a symmetric factorial experiment. When the block size of the experiment permits only a sub-set of the factorial combinations to be assigned to the experimental units within a block, resort is made to the theory of confounding. With respect to symmetric factorial designs, the theory of confounding has been highly developed by Bose [1], Bose and Kishen [4], and Fisher [11], [12]. An excellent summary of the results of this research appears in Kempthorne [13]. However, these researches are closely related to Galois field theory resulting in (i) only symmetric factorial designs being incorporated into the current theory of confounding; (ii) the common level must be a prime (or power of a prime) number; and (iii) the block size must be a multiple of this prime number. The theory of confounding for asymmetric designs has not been developed to any great degree. Examples of asymmetric designs can be found in Yates [19], Cochran and Cox [9], Li [15], and Kempthorne [13]. Nair and Rao [16] have given the statistical analysis of a class of asymmetrical two-factor designs in considerable detail. Kramer and Bradley [14] discuss the application of group divisible designs to asymmetrical factorial experiments, however their paper is mainly confined to the two-factor case and its intra-block analysis. It is the purpose of this paper, which was done independently of their work, to outline the general theory for using the group divisible incomplete block designs for asymmetrical factorial experiments. The use of incomplete block designs for asymmetric factorial experiments results in (i) no restriction that the levels must be a prime (or power of a prime) number, (ii) no restriction with respect to the dependence of the block size on the type of level, and (iii) unlike the previous referenced works on asymmetric factorial designs, the resulting analysis is simple, does not increase in difficulty with an increasing number of factors, and "automatically adjusts" for the effects of partial confounding. Section 2 states three useful lemmas, Section 3 contains the main results of this paper, and Section 4 outlines the recovery of inter-block information.

In an earlier paper [4], the author has given upper bounds for the number of disjoint blocks in (i) Semi-regular GD designs, (ii) certain PBIB designs with two associate classes having triangular association scheme, (iii) certain PBIB designs with two associate classes having $L_2$ association scheme and (iv) certain PBIB designs with three associate classes having rectangular association scheme. In this paper, we give bounds for the number of common treatments between any two blocks of the above-mentioned PBIB designs. The main tools used to establish the results of this paper are the theorems proved by (i) Bose and Connor [1], (ii) Raghavarao [3], and (iii) Vartak [6].

1. Preliminaries. Let ,u be a given probability measure on (X, B), where X is some finite dimensional Euclidean space and B is the class of Borel sets on X. For each 0 E X, let Il6(A) = p(A-0), where A C B and A-0 = {x: x+0 c A}. A set 'A' is called ,-invariant if ilo(A) = p(A) V 0 E X. For example the null set 0 and the whole space X are trivially p-invariant. The class of all p-invariant sets is denoted by A(,u). A set 'A' is called "non-trivial" if 0 < ,l(A) < 1. That "nontrivial" p-invariant sets exist is seen by noting that if ,I assigns probability I each to {O} and {1}, then A is ,u-invariant if and only if A' = A+1, e.g., A = -O (2n, 2n+ 1] is p-invariant with p(A) = 2. It is easily seen that A(,) is a monotone class, is closed for complementation and disjoint unions, and is not necessarily a r-algebra. The probability measure ,u is called weakly incomplete (weaklycomplete) if it has (or does not have) non-trivial It-invariant sets. The results we present here have originated from a paper of Basu and Ghosh (1969) on p-invariant sets. Our main object is to make a careful study of some of the conjectures contained in their paper. A brief account of the results contained in the paper is as follows

In a recent paper A. N. Shiryaev [1] discusses the problem of detecting the arrival of a "disorder" in an observed stochastic process, as quickly as possible subject to a limitation on the number of false alarms. He considers two versions of a simple model. In the first, the disorder arrives at a discrete instant $\theta$ according to a geometric distribution. The process disturbed by this event consists of a sequence of independent observations $\{\xi_t\}$, such that $\xi_1, \xi_2, \cdots, \xi_{\theta - 1}$ arise from a certain distribution $F_0$, whereas $\xi_\theta, \xi_{\theta + 1}, \cdots$ come from a different distribution $F_1$. In the continuous time version of the model, the a-priori distribution of $\theta$ is exponential: $P(\theta > t) = e^{-\lambda t} \quad (t \geqq 0)$ and the disorder is represented by a change in the mean drift of an observed Wiener process $\{\eta(t)\}$. More precisely, for any given value of $\theta$, this process has independent normal increments $\delta\eta = \eta(t + \delta t) - \eta(t)$, with \begin{align*}E (\delta\eta) = 0 \quad (0 \leqq t < \theta), \notag \\ E(\delta\eta) = \delta t \qquad (t \geqq \theta), \notag \\ \operatorname{Var} (\delta\eta) = \delta t \quad (t \geqq 0)\end{align*}. In both versions it may be decided at any instant $t$ to carry out a detailed inspection in order to ascertain whether or not the disturbance has occurred. Then, if it is found that $\theta < t$ the process terminates but observation must be resumed immediately after a false alarm. Within these rules it is required to find a decision procedure which determines the instants at which a thorough inspection is worthwhile. Assuming that $N$, the expected number of false alarms, is specified in advance Shiryaev establishes the general form of policy which minimizes $\tau$, the expected delay in verifying the arrival of the disorder. The a posteriori distribution of $\theta$ at any time, does not depend on anything which took place before the last false alarm. For example, in continuous time $p(t) = P(\theta \leqq t \mid \eta(t'), 0 \leqq t' \leqq t) = P(\theta \leqq t \mid \eta(t'), s \leqq t' \leqq t),$ where $s$ is the instant of the most recent false alarm. The geometric and exponential distributions have the useful property that $P(\theta > t + s \mid \theta > s) = P(\theta > t \mid \theta > 0).$ He deduces that the optimal policy for the period following any false alarm must correspond exactly with the procedure applied initially, before the first inspection. In addition, he proves the existence of a critical level $p^\ast = p^\ast(N)$ such that, in general, observations should continue so long as $0 \leqq p(t) < p^\ast$ with an immediate inspection as soon as $p(t) \geqq p^\ast$. These and other similar results are established first for the discrete time model and then extended to the continuous time version. For the latter, the paper also gives more explicit calculations: the evaluation of $\tau$ in terms of $p^\ast$, for example. But no attempt is made to determine the critical level $p^\ast(N)$ for the optimal policy. In fact, as we shall see, a very simple relation holds: $p^\ast (N) = (N + 1)^{-1}.$ However, the aim here is to show how the optimal policy can be found for a more realistic specification of the minimization problem, involving given delay and inspection costs. We shall concentrate entirely on the continuous time model and suppose that each inspection incurs an instantaneous cost $K > 0$, not depending on its outcome, whereas any delay in detecting the arrival of the disorder leads to a cost $c > 0$ per unit time. Hence the total expected cost is $K(N + 1) + c\tau$, which depends both on the decision procedure and on the initial condition $p(0) = 0$. The minimization will be based on the calculation of the minimum expected future cost $f_\ast(\varphi)$, as a function of the current state $\varphi(t) = p(t)/(1 - p(t))$, by solving a certain differential equation with special boundary conditions. A heuristic argument, in which one simply assumes that $f_\ast(\varphi)$ is suitably differentiable, can be given without much difficulty. But, strictly speaking, it is not clear that risk functions such as $f_\ast(\operatorname{var})$, each of whose values is defined as the infimum of a class of expectations, are sufficiently well behaved. This difficulty is often encountered in statistical applications of dynamic programming to processes in continuous time. Typically, it is extremely difficult to establish the required differentiability properties directly and it is necessary to seek an indirect justification by means of existence and uniqueness theorems. In our case the formal solution can be produced explicitly and, because of this, its justification is much easier. Nevertheless, the approach is complicated by the need to establish several preliminary results, and the discussion of these special properties is limited to a brief indication of the main steps, in the hope that the essential structure of the argument will be more generally useful. Section 2 is concerned with the information process $\{\varphi(t)\}$. Its relation to the observed process $\{\eta(t)\}$ is described and certain properties of its increments are collected for later use. The main argument begins in Section 3 with a discussion of sub-optimal decision procedures defined by specifying an open continuation set $\mathscr{C}$ within the space $\lbrack0, \infty)$ of possible "initial" states $\varphi$. It is shown that any risk function $f(\varphi)$ can be determined for each sub-interval of the corresponding set $\mathscr{C}$ by solving the basic differential equation appropriately. Sections 4 and 5 consider the special solution $f_\ast(\varphi)$ which represents the optimal decision procedure, and give the required verification that $f_\ast(\varphi)$ is uniformly minimal. The final section contains a brief analysis of the operating characteristics of the optimal policy and indicates the importance of evaluating the particular minimum risk $f_\ast(0)$.

Since the notion of completeness for a family of distributions was introduced by Lehmann and Scheffe [7], a problem of interest has been to determine conditions under which a complete sufficient statistic exists for a family of multivariate normal distributions. One approach to this problem, first formulated for a completely random model in some work by Graybill and Hultquist [2] and extended to a mixed linear model by Basson [1], has a basic assumption of commutativity for certain pairs of matrices. In the present paper some of the commutativity conditions and an associated eigenvalue condition assumed in the theorems on completeness in both [1] and [2] are replaced by the weaker requirement of a quadratic subspace. These subspaces, i.e., quadratic subspaces, are introduced and briefly investigated in Section 2 and are found to possess some rather interesting mathematical properties. The existence of $\bar\mathscr{A}$-best estimators (e.g., [12]) is also examined for several situations; and it is found that the usual estimators in the weighting factors for the recovery of interblock information in a balanced incomplete block design (treatments fixed and blocks random) have an optimal property when the number of treatments is equal to the number of blocks. Throughout the paper $(\mathscr{A}, (-,-))$ denotes the FDHS (finite-dimensional Hilbert space or finite-dimensional inner product space) of $n \times n$ real symmetric matrices with the trace inner product. The notation $Y \sim N_n(X\beta, \sum^m_{i=1} \nu_iV_i)$ means that $Y$ is an $n \times 1$ random vector distributed according to a multivariate normal distribution with expectation $X\beta$ and covariance matrix $\sum^m_{i=1} \nu_iV_i$; and for such a random vector the following is assumed: (a) $X$ is a known $n \times p$ matrix and $\beta$ is an unknown vector of parameters ranging over $\Omega_1 = R^p$. (b) Each $V_i(i = 1,2,\cdots, m)$ is a known $n \times n$ real symmetric matrix, $V_m = I$, and $\nu = (\nu_1,\cdots, \nu_m)'$ is a vector of unknown parameters ranging over a subset $\Omega_2$ of $R^m$. (c) The set $\Omega_2$ contains a non-void open set in $R^m$ and $\sum^m_{i=1} \nu_iV_i$ is a positive definite matrix for each $\nu \in \Omega_2$. (d) The parameters $\nu$ and $\beta$ are functionally independent so that the entire parameter space is $\Omega = \Omega_1 \times \Omega_2$. For the special case when $X = 0$ the notation $Y \sim N_n(0, \sum^m_{i=1} \nu_iV_i)$ is used and for this situation the parameter space $\Omega$ reduces to $\Omega_2$. The notation and terminology in the following sections is generally consistent with the usage in [12]. The adjoint of a linear operator $\mathbf{T}$ is denoted by $\mathbf{T}^\ast$ and the transpose of a matrix $A$ is denoted by A'. Additionally, the unique Moore-Penrose generalised inverse of a matrix $A$ is denoted by $A^+$, and as in [12], only real finite-dimensional linear spaces are considered.

Let $\mathbf{x}$ and $\mathbf{\theta}$ denote $s$-dimensional column vectors. The components $x_1, x_2,\cdots x_s$ of $\mathbf{x}$ are random variables jointly following an $s$-variate distribution and components $\theta_1, \theta_2,\cdots, \theta_s$ of $\mathbf{\theta}$ are real numbers. The random vector $\mathbf{x}$ is said to follow an $s$-variate Exponential-type distribution with the parameter vector (pv) $\mathbf{\theta}$, if its probability function (pf) is given by \begin{equation*}\tag{1.1} f(\mathbf{x}, \mathbf{\theta}) = h(\mathbf{x}) \exp \{\mathbf{x'\theta} - q(\mathbf{\theta})\},\end{equation*} $\mathbf{x} \varepsilon R_s$ and $\mathbf{\theta} \varepsilon (\mathbf{a}, \mathbf{b}) \subset R_s. R_s$ denotes the $s$-dimensional Euclidean space. The $s$-dimensional open interval $(\mathbf{a}, \mathbf{b})$ may or may not be finite. $h(\mathbf{x})$ is a function of $\mathbf{x}$, independent of $\mathbf{\theta}$, and $q(\mathbf{\theta})$ is a bounded analytic function of $\theta_1, \theta_2,\cdots \theta_s$, independent of $\mathbf{x}$. We note that $f(\mathbf{x}, \mathbf{\theta})$, given by (1.1), defines the class of multivariate exponential-type distributions which includes distributions like multivariate normal, multinomial, multivariate negative binomial, multivariate logarithmic series, etc. This paper presents a theoretical study of the structural properties of the class of multivariate exponential-type distributions. For example, different distributions connected with a multivariate exponential-type distribution are derived. Statistical independence of the components $x_1, x_2,\cdots, x_s$ is discussed. The problem of characterization of different distributions in the class is studied under suitable restrictions on the cumulants. A canonical representation of the characteristic function of an infinitely divisible (id), purely discrete random vector, whose moments of second order are all finite, is also obtained. $\varphi(\mathbf{t}), m(\mathbf{t}), k(\mathbf{t})$ denote, throughout this paper, the characteristic function (ch. f.), the moment generating function (mgf), and the cumulant generating function (cgf), respectively, of a random vector $\mathbf{x}$. The components $t_i$ of the $s$-dimensional column vector $\mathbf{t}$ are all real.

This paper demonstrates the direct relationship which exists between $O(p^m, p^m - 1)$ sets and a balanced set of $\ell$-restrictional lattice designs for $p^m$ treatments. For instance, we will show that \begin{equation*}A = \begin{bmatrix}0 & 1 \\ 1 & 1\end{bmatrix}\end{equation*} which, as has been shown by Raktoe [5] completely specifies a balanced set of 2-restrictional lattice designs for $7^2 = 49$ treatments, will also completely characterize a set of 48 mutually orthogonal latin squares of order 49, i.e. an $O(49, 48)$ set. In other words, if our interest is to exhibit an $O$(49, 48) set, the above $2 \times 2$ matrix will do the job. Strangely enough, as will be shown, $A$ also completely characterizes an $O$(4, 3) set. Note that, since a balanced set of 1-restrictional lattice designs is simply a BIB design, this paper shows in particular a different proof for the known equivalence of the $O(p^m, p^m - 1)$ sets with a class of resolvable BIB designs. Consequently, the content of this paper will be useful for those who are concerned with tabulating the designs or writing an efficient program for generating designs on a computer.

Consider $n$ boxes, each box having an associated probability, $p_i, \big(\sigma_i p_i = 1\big)$, and an associated integer, $k_i$. If balls are thrown one by one into these boxes, the probability being $p_i$ that any one ball falls into the $i$th box, then the number of balls which must be thrown in order to obtain, for the first time, at least $k_{i_1}$ balls in the $i_1$th box, at least $k_{i_2}$ balls in the $i_2$th box, $\cdots$, and at least $k_{i_s}$ balls in the $i_s$th box, is a random variable, $N_s\lbrack k_1(p_1), k_2(p_2), \cdots, k_n(p_n)\rbrack$. Here $i_1, i_2, \cdots, i_s$ represent the numbers of that set of $s$ boxes, $(1 \leq s \leq n)$, which first satisfies the stated condition. The distribution of $N_s\lbrack k_1(p_1), k_2(p_2), \cdots, k_n(p_n)\rbrack$ can be written down for any set of values assigned to $n, s$, the $p_i$'s and the $k_i$'s. However, for $n$ greater than 2 the distribution assumes such an extremely complicated multinomial form that except for certain special cases even the mean of the distribution cannot be numerically evaluated without a prohibitive amount of labor. This paper presents the exact moments of $N_1\lbrack k_1(p_1), k_2(p_2)\rbrack$ and $N_2\lbrack k_1(p_1), k_2(p_2)\rbrack$ in forms that readily lend themselves to computation and shows how these moments can be used to obtain approximate values for the mean and variance for certain situations where $n$ is greater than two. These approximation formulae are given for 1. The mean and variance, for any $n$ and any set of $k_i$'s and $p_i$'s when $s = 1$ or $n$. 2. The mean, for any $n$ and $2 \leq s \leq n - 1$, when $p_i = 1/n, k_i = k, (i = 1, 2, \cdots, n)$. Some indications are given concerning the error of the approximations, and the circumstances which lead to a minimum (and maximum) error. Curves have been prepared to show the mean for the two box case, the primary function of these curves being to assist in the application of the approximation formulae. Some problems where the results of this paper might be applicable are suggested in the Introduction.

Majinder [3] obtained an upper bound for the number of disjoint blocks in BIB designs. In this paper we give an upper bound for the number of disjoint blocks in (i) Semi-regular GD designs, (ii) PBIB designs with two associate classes having triangular association scheme, (iii) PBIB designs with two associate classes having $L_2$ association scheme, and (iv) PBIB designs with three associate classes having rectangular association scheme. The main tools used to establish the results of this paper are the theorems proved by (i) Bose and Connor [1], (ii) Raghavarao [4] and (iii) Vartak [6].

Let Z = {O, 1, 2} and define two binary operations /\ and V on Z as follows: 0/\ 1 = 0,0 V 1 = 1, 1 /\ 2 = 1,1 V 2 = 2,2 A 0 = 2, 2 V 0 = 2, both operations are idempotent and commutative. This paper deals with the equational class Z generated by the algebra . The class Z contains the class of all distributive lattices and Z is a subclass of the class of weakly associative lattices (trellis, T·lattice) in the sense of E. Fried and H. Skala. The purpose of this paper is to prove that Z shares the most important properties of the class of distributive lattices.

In this paper we prove several asymptotic results about the expected length of time until first passage of a vector valued random walk. We suppose $X_i = (X^1_i, \cdots, X^k_i), i \geqq 1$, is a sequence of independently and identically distributed random vectors. We assume throughout that \begin{equation*}\tag{1}\max_{1 \leqq j \leqq k}E|X^j_1| < \infty; \mu_j = EX^j_1, 1 \leqq j \leqq k; \end{equation*} \\ \begin{equation*} \text{and that} 0 < \min_{1 \leqq j \leqq k} \mu_j.\end{equation*} We consider the following kind of first passage problem. Let $p(\cdot, \cdots, \cdot)$ be a real valued function of $k$ variables. Given $c > 0$ define a stopping variable $N(c) \geqq 1$ to be the least integer $n$ such that \begin{equation*}\tag{(2)}p \big (\sum^n_{i=1} X^1_i, \cdots, \sum^n_{i=1} X^k_i\big) > c,\end{equation*} with $N(c) = \infty$ if the inequality (2) fails for all $n \geqq 1$. The main result of this paper is: THEOREM 1. Suppose the function $p(\cdot, \cdots, \cdot)$ is a homogeneous function of degree one. Given the above assumptions, with probability one $\lim_{c\rightarrow\infty} c^{-1}N(c) = 1/p(\mu_1, \cdots, \mu_k)$. Suppose there is a real number $\alpha > 0$ such that \begin{equation*}\tag{3}\text{if} \min_{1 \leqq j \leqq k} a_j \geqq 0 \text{then} \alpha p(a_1, \cdots, a_k) \geqq \min_{1\leqq j \leqq k} a_j.\end{equation*} Then \begin{equation*}\tag{4} \lim_{c\rightarrow\infty}E|c^{-1} N(c) - 1/p(\mu_1, \cdots, \mu_k)| = 0.\end{equation*} If one views Theorem 1 in the light of Doob [2] Theorem 1 becomes very plausible. It is natural to define a continuous parameter process \begin{equation*}\tag{5}X(c) = c - p\big(\sum^{N(c) -1}_{i=1} X^1_i, \cdots, \sum^{N(c)-1}_{i=1} X^k_i\big).\end{equation*} In case the random variables $X^1_1, \cdots, X^k_1$ are nonnegative, using additional assumptions about $p(\cdot, \cdots, \cdot)$ it can be shown that asymptotically as $c \rightarrow \infty$ the process $X(\cdot)$ becomes a stationary Markov process. We plan to examine this question further in another place. The language of this paper is that of random variables and probability. We use freely the idea of stopped random walks. This makes it necessary to define, in the sequel, many different stopping variables. To simplify notation we use the same notation for different stopping variables and leave it to the context to distinguish the various random variables. Theorem 1 is a corollary of Theorem 3, stated below. The sequence of the argument is to prove a one-dimensional result, Theorem 2, then to prove by mathematical induction a $k$-dimensional result, Theorem 3, for the choice $p(x_1, \cdots, x_k) = \min_{1 \leqq j \leqq k} x_j$. The statements of Theorem 2 and Theorem 3 follow. THEOREM 2. Suppose $\{X_i, i \geqq 1\}$ is a sequence of independently and identically distributed random variables such that $E|X_1| < \infty \text{and} EX_1 = \mu > 0.$ If $c > 0$ is a real number define an integer valued random variable $N(c)$ to be the least integer $n \geqq 1$ such that $X_1 + \cdot + X_n > c$, with $N(c) = \infty$ if for all $n \geqq 1, X_1 + \cdot + X_n \leqq c$. Let $h(\cdot)$ be a real valued continuous strictly increasing convex function defined on $\lbrack 0, \infty)$ such that $h(0) = 0$ and $\lim_{x\rightarrow\infty} h(x)/x = \infty$. Assume that $Eh(|X_1|) \leqq \Delta < \infty$. Then $\mathrm{(6)}P(N(c) < \infty) = 1; EN(c) < \infty;$ $c \leqq \mu EN(c) \leqq c + h^{-1}(\Delta EN(c)).$ Convex functions of the type mentioned in the statement of Theorem 2 always exist. We discuss this question briefly at the beginning of Section 2. THEOREM 3. Suppose $\{X_i, i \geqq 1\}$ is a sequence of independently and identically distributed $k$-dimensional random vectors satisfying (1). Let $p(x_1, \cdots, x_k) = \min_{1 \leqq j \leqq k} x_j$ and let $N(c)$ be defined as in (2). Then $\mathrm{(7)}P(N(c) < \infty) = 1; EN(c) < \infty;$ $\lim_{c\rightarrow\infty} c^{-1}EN(c) = 1/(\min_{1 \leqq j \leqq k}\mu_j).$` We prove Theorem 2 in Section 2 for the sake of completeness and in order to have a result including a uniformity condition. Theorem 3 does not have any uniformity condition. Theorem 4 is a partial generalization of Theorem 2 in regard to a uniformity condition. THEOREM 4. Assume the hypotheses and definitions of Theorm 3. In addition assume that if $2 \leqq j \leqq k, i \geqq 1$, then $X^j_i \geqq 0$, and that $0 < \mu_1 \leqq \mu_2 \leqq \cdot \leqq \mu_k$. Let $h(\cdot)$ be a real valued nonnegative continuous function defined on $\lbrack 0, \infty)$ which satisfies \begin{equation*}\tag{(8)}h(0) = 0; \lim_{x\rightarrow\infty}h(x) /x = \infty.\end{equation*} There exists a function $a_k(\cdot, \cdot, \cdot)$ of three variables (and also depending on $h(\cdot)$ such that if $\mu > 0, \Delta > 0$ then $\lim_{c\rightarrow\infty} a_k(c, \mu, \Delta) = 0$ and if \begin{equation*}\tag{(9)}\max_{1 \leqq j \leqq k} Eh(|x^j_1|) \leqq \Delta, \min_{1 \leqq j \leqq k}EX^j_1 \geqq \mu_1,\end{equation*} then \begin{equation*}\tag{(10)}1/\mu_1 \leqq c^{-1}EN(c) \leqq 1/\mu_1 + a_k(c, \mu_1, \Delta).\end{equation*} The statement of Theorem 4 is asymmetric in that we require $X^2_1, \cdots, X^k_1$ to be nonnegative random variables. We believe that this restriction can be removed. But we have not been able to do so using the methods of this paper. The possibility of proving Theorems 2 and 4 (thereby obtaining results with uniformity conditions) was suggested to the author by arguments in a paper by Kiefer and Sacks [4]. Both Theorems have application to the study of the asymptotic behavior of the expected sample size in sequential tests. In regard to Theorem 2, since $\lim_{x\rightarrow\infty} h(x)/x = \infty$, if $d > 0$ then $\lim_{x\rightarrow\infty} h^{-1} (dx)/x = d \lim_{y\rightarrow\infty} h^{-1}(y)/y = d \lim_{z\rightarrow\infty} z/h(z) = 0$. Therefore from (6) it follows that $\lim_{c\rightarrow\infty} c^{-1} EN(c) = \mu^{-1}$. This part of Theorem 2 is known. The results of this paper on the length of time to first passage are related to the problems of renewal theory. We refer the reader to Smith [6] for a summary of results. The only multidimensional result, along the lines of this paper, in print, seems to be that of Chung [1]. In he proofs we use freely the idea of a stopped random walk and in connection with this an identity due to Wald [7]. Because this identity is used repeatedly we state it here. Suppose $\{Z_n, n \geqq 1\}$ is a sequence of independently and identically distributed random variables and $E|Z_1| < \infty$. Suppose $N$ is a random variable taking only positive integer values and $EN < \infty$. Suppose for each integer $n \geqq 1$ the event $\{N \geqq n\}$ is independent of the random variables $\{Z_m, m \geqq n\}$. Then $E\|Z_1 + \cdots + Z_N\| < \infty \text{and} E(Z_1 + \cdots + Z_N) = (EN)(EZ_1)$. Throughout the remainder of this paper we refer to this as Wald's identity and omit further mention of the reference. In the proofs given below many of the arguments require the definition of new stopping variables. For the sake of brevity the definitions of these stopping variables omit the statement that the value is $\infty$ if the stated condition fails to hold for any positive integer $n$. In this context the meaning of statements like "$P(N < \infty) = 1$" is that the exceptional set in question has measure zero. The proof of Theorem 2 is given in Section 2. The proofs of Theorem 3 and Theorem 4 require several lemmas proven in Section 3. The proof of Theorem 3 is given in Section 4, of Theorem 4 in Section 5, and of Theorem 1 in Section 6. The author is indebted to W. L. Smith for the present form of the statement of Lemma 3 and also for a very much shorter proof.

In a previous paper [8] the asymptotic behavior of a class of invariant sequential probability ratio tests was studied to the extent of establishing termination with probability one. In this paper, under somewhat stronger conditions, certain bounds on the distribution of sample size will be obtained. The statistical framework is as follows: $Z_1, Z_2, \cdots$ is a sequence of independent and identically distributed (iid) random vectors with values in Euclidean $k$-space $E^k$. The common distribution is at first assumed to belong to the family $\mathscr{N}$ of all nondegenerate $k$-variate normal distributions. On $E^k$ there acts a group $G^\ast$ of affine transformations (precise assumptions on $G^\ast$ are given in Section 2). Let $V_1, V_2, \cdots$ be a maximal invariant sequence obtained from $Z_1, Z_2, \cdots$ under the application of $G^\ast$. Since every transformation in $G^\ast$ sends a member of $\mathscr{N}$ into a member of $\mathscr{N}, G^\ast$ also acts on $\mathscr{N}$. Let $\gamma$ be a maximal invariant function on $\mathscr{N}$, then the joint distribution of $V_1, V_2, \cdots$ depends only on $\gamma$. Denote the distribution of $(V_1, \cdots, V_n)$ by $P_{n\gamma}$. Let $\gamma_1, \gamma_2$ be two distinct values of $\gamma$, let $r_n = dP_{n\gamma_2}/dP_{n\gamma_1}$ (set equal to $\infty$ wherever $P_{n\gamma_2}$ is not absolutely continuous with respect to $P_{n\gamma_1}$) and put $R_n = r_n(V_1, \cdots, V_n)$. Then an invariant sequential probability ratio test, based on the sequence $\{R_n\}$, is defined by choosing stopping bounds $B < A$, letting the stopping variable $N$ be the smallest $n$ such that $R_n \leqq B$ or $\geqq A$, and accepting $\gamma_1$ or $\gamma_2$ according as $R_N \leqq B$ or $\geqq A$. Once the sequence $\{R_n\}$ has been defined we are at liberty to study its behavior when the actual common distribution of the $Z_n$ is not necessarily on the orbit of $\gamma_1$ or of $\gamma_2$ or, for that matter, is not even a member of $\mathscr{M}$. Still assuming $Z_1, Z_2, \cdots$ to be iid, the common distribution $P$ will be assumed to be a member of $\mathscr{P}$, to be defined later, where $\mathscr{P} \supset \mathscr{M}$. The joint distribution of $Z_1, Z_2, \cdots$ will also be denoted $P$. The object is to establish a bound on $P(N > n)$ as a function of $n$, for each $P \varepsilon \mathscr{P}$. Results on sample size distribution of invariant sequential probability ratio tests are very scarce. Ifram [5] considered a certain class of problems and obtained an exponential bound on $P(N > n)$, where $P$ is a member of the original model and should not belong to a certain exceptional set of distributions for which no results could be obtained. Sacks [6] also obtained an exponential bound in the case of the sequential $t$-test (as a by-product of other results), again excluding certain exceptional $P$'s. Savage and Sethuraman [7] obtained an exponential bound in a nonparametric problem, a sequential rank test. They allowed $P$ to be outside the original model, but again for a certain set of exceptional $P$'s no results could be obtained. In the present paper we shall establish, under Assumptions A and B (Section 2), an exponential bound of the form $P(N > n) < c\rho^n$ for some $\rho < 1$, except, again, for $P$'s in a certain set. For these exceptional $P$'s, however, we also obtain results, even though weaker, of the form $P(N > n) < c\rho^{n^{1/3}}$ (under an additional assumption on the function $\Phi$ of Section 2). This result is still strong enough to assert the existence of all moments of $N$, although not the existence of a moment generating function as is the case if $P(N > n)$ has an exponential bound. Thus, our results are more general and stronger in some respects than those of Ifram [5], but Ifram does give a precise value of the smallest possible $\rho$ in the exponential bound, whereas we have nothing comparable to offer.

In a single-server first-come-first-served queue the waiting-times of successive customers are related by the equation \begin{equation*}\tag{1}w_{n + 1} = \lbrack w_n + U_n\rbrack^+\end{equation*} where \begin{equation*}\tag{2}U_n = S_n - T_n.\end{equation*} Here $S_n$ and $T_n$ are the service-time of the $n$th customer, and the time between the arrivals of the $n$th and the $(n + 1)$th customers, respectively. In the particular case of mutually independent identically distributed $U_n$ the basic investigation of this equation was carried out by Lindley [1], who found a simple necessary and sufficient condition for the existence of a stationary waiting-time distribution and derived this distribution in certain special cases. The theory was developed by Smith [2], who under fairly weak conditions gave a systematic treatment of the Wiener-Hopf equation obtained by Lindley. In the less restricted case when $U_n$ is a strictly stationary process it has been shown by the author (Loynes [3]) that under a simple condition the existence of a unique stationary distribution is again ensured: it is the purpose of this paper to show how (when this condition is satisfied) the stationary distribution may sometimes be found, and to obtain some qualitative results. The theory will be developed in Sections 3 and 4, and some examples discussed in Section 5. On the assumption that $U_n$ is a metrically transitive sequence the condition just referred to is \begin{equation*}\tag{3}E\lbrack U_n\rbrack < 0,\end{equation*} and we shall therefore suppose this satisfied throughout the paper. The assumption that $U_n$ is metrically transitive does not affect most of the arguments in this paper, but it will be made for convenience. For the existence of a unique stationary distribution (3) is both necessary and sufficient, but there is sometimes more than one stationary distribution when the inequality in (3) is replaced by equality. Such situations have been ignored here for several reasons: they are not very common, some of the arguments either break down or need adaptation, and in any case the problems are not then as difficult, for it follows from equation (7) of [3] that the function $\psi$ occurring in (5) below is then identically equal to one, so that the only unknown is $\phi$. There is never a stationary distribution when the inequality in (3) is reversed. Throughout the entire investigation we shall suppose the queue has a structure which satisfies the following condition (H). This is actually no restriction at all when the queue is in the stationary state, since the variables $z_n$ occurring in it may be taken as $(W_{n + 1}, T_{n + 1})$, where $\{W_n\}$ is the stationary waiting-time sequence. However, all the results will refer to the distribution of the waiting-time conditional on $z_n$, so that it will always be tacitly assumed that the distribution of $z_n$ is known in order to allow deductions about the unconditional distribution of the waiting-time. (H): There exists a sequence $\{z_n\}$ (defined on the same probability space as $w_n$) of random vectors--i.e., in finite-dimensional Euclidean space--with the following properties: (i) $\{z_n, S_n, T_n\}$ is a strictly stationary process. (ii) $S_n, T_n$, and $w_n$ are conditionally independent given $z_{n - 1}, z_n$. (iii) $w_n$ and $z_n$ are conditionally independent given $z_{n - 1}$. The assumption that (H) is satisfied allows us to write down the equation satisfied by the stationary (conditional) waiting-time distribution function. We cannot, however, in such a general situation actually find the solution to the equation, and to discover appropriate further restrictions which may make this possible we may consider further the case treated by Lindley and Smith. The general solution given by Smith was analytically complex and apparently only obtainable from the Wiener-Hopf technique or the equally specialized method due to Spitzer [4]. If, however, either the service-times or the inter-arrival times had a distribution with a rational characteristic function the solutions were much simpler in form, and in at least a few cases had been obtained previously by other methods. With this in mind we impose similar conditions here on the conditional characteristic functions; on that of the interarrival time in Section 3, and on that of the service-time in Section 4. The lack of success in treating the problem without these restrictions is probably no great loss in practice, in view of the complex nature of the Wiener-Hopf solution for the simple case. The results obtained under the conditions imposed so far are in the nature of aids to the solution of the problem, rather than the solution itself. A simple situation for which the required distribution may then be obtained straightforwardly occurs when the following "finite-matrix" condition is satisfied: (HF): Condition (H) holds, and $z_n$ has (with probability one) only a finite number $k$ of different possible values. An interesting result obtained by Smith showed that, roughly speaking, the characteristic functions of the waiting-time and the service-time had the same number of poles, and a somewhat similar result related the distribution of the inter-arrival times to that of the waiting-time. Under (HF) it will be found that similar results are also true. Smith in fact gave explicit formulae of a simple type for the two special cases, but we shall content ourselves here with pointing out how corresponding formulae could be obtained, since it appears that they are no longer simple when $k$ has a value other than one. As we have already remarked, all simple queues are included in (H) when in the stationary state. Even under the condition that the distribution of $z_n$ be known, a large class of queues satisfies (H), such as that in which $S_n$ and $T_n$ are independent stationary Markov processes. An example of a queue of considerable interest which apparently does not admit a specification of this type is that in which customers are due at regular intervals but are late independently with a lateness distribution which extends to $\infty$ (if the lateness distribution and service time distribution are both negative exponential, then (H) is satisfied, and a brief discussion of this example will be found in Section 5). It will be seen that by taking $z_n = 1$ the classical case with independence is included under (HF); two other types of queue satisfying (HF) are of some interest, and are discussed in Section 5--one being a simple queue whose input is a mixture of two streams of customers, and the other a queue whose input consists of customers who have already been served in a first queue. In addition to any other queues which may fall into this class, it is presumably true, that any queue may be approximated by those of this "soluble" class, although there are of course very great difficulties in deciding how such an approximation should be carried out. Finally we observe that since the content of a semi-infinite dam in discrete time is described by the same equation (1), the results obtained here may be applied in that context also, and in particular the finite-matrix case gives a class of dams with serially dependent inputs for which explicit solutions can be found.

In the definition of a two-person zero-sum game given by Von Neumann and Morgenstern it is assumed that both players know the rules of the game (e.g., the game tree, the information sets as well as the distributions of the ensuing payoffs for given strategy choices, etc.). We use the term pseudo-game to denote the case where at least one player does not have complete information. In this paper we restrict our attention to those pseudo-games in which player I, say, is only aware of his set of pure strategy choices (assumed to contain $m$ elements: $2 \leqq m < \infty$) and not of player II's strategy choices (assumed to have uniformly bounded second moments). Player II is assumed to have complete information. More precisely, we shall study pseudo-games $G$ that have the format given below: Let $A = \{a_1, \cdots, a_m\}$ denote the pure strategy choices of player I. Denote by $A^\ast$ the set of probability distributions $p$ over $A$ (player I's mixed strategy choices). We sometimes write $p$ in the form $(p(1), \cdots, p(m)), \sum^m_{j=1}p(j) = 1$, and $p(j) \geqq 0$, with the interpretation that when player I uses $p$ he will play $a_j$ with probability $p(j)$. Any element of $A^\ast$ that assigns mass 1 to some $a \varepsilon A$ will be simply denoted by $a$. Let $B$ denote the set (not necessarily finite) of pure strategies for player II. Let $\mathscr{B}$ be a fixed $\sigma$-field of subsets of $B$ and denote by $B^\ast$ the set of all probability distributions $q$ over $\mathscr{B}$ (player II's mixed strategies). We assume that $\mathscr{B}$ contains all single point sets of $B$, so that $B^\ast$ contains all finite probability distributions over $B$. We postulate that we are given for each pair $(a, b)$ in the product space $A \times B$ a distribution $P_{(a, b)}$ on the real line which represents the distribution of the loss incurred by player I (or gain by player II) if $a \varepsilon A$ is the strategy choice of I and $b \varepsilon B$ is the strategy choice of II. Contrary to the usual practice, the payoff for given pure strategy choices is thus allowed to be random. We do this in order that our main results may be proved in greater generality. An example of a pseudo-game with random payoffs is given in Section 2. The distributions $P_{(a,b)}$ are assumed to have uniformly bounded second moments. For each $a \varepsilon A$, and fixed Borel set $C, P_{(a,\cdot)}(C)$ is assumed to be $\mathscr{B}$-measurable. For each pair $(a, b) \varepsilon A \mathbf{\times} B$, let $X_{(a,b)}$ be a random variable having $P_{(a,b)}$ as its distribution. Suppose that players I and II are using strategies $p$ and $q$, respectively. They can determine the payoff of the pseudo-game by first selecting an $a \varepsilon A$ and a $b \varepsilon B$ according to the distributions $p$ and $q$, respectively, and then treating an observed value of $X_{(a,b)}$ as the payoff. For every pair of strategies $(p, q)$ that players I and II may use we define the expected value of the payoff $R(p, q)$ by means of the equation: \begin{equation*}\tag{1.1} R(p, q) = \sum^m_{j=1} p(j) \int \lbrack\int x dP_{(a_j,b)}(x)\rbrack dq(b).\end{equation*} We are assuming that player I is only aware of the set $A$, while player II has complete information. However, by assuming instead that player I is also aware of the set $B$ as well as the distributions $P_{(a,b)}, (a, b) \varepsilon A \times B$, we can associate with every such pseudo-game $G$ a game with complete information $G'$. Such concepts as "value" and "minimax strategy" do not carry over to pseudo-games. However by the minimax theorem, since $A$ is assumed finite, every such game $G'$ will have a value $v_G$ and player I will have a minimax strategy $p'$: \begin{equation*}\tag{1.2)} v_G = \sup_{q\varepsilon B^\ast} R(p', q) = \inf_{p\varepsilon A^\ast} \sup_{q\varepsilon B^\ast} R(p, q) = \sup_{q\varepsilon B^\ast} \inf_{p\varepsilon A^\ast} R(p, q).\end{equation*} Suppose now that players I and II are playing a sequence of identical pseudo-games of the type we have been describing; i.e., they play one game, observe their losses and play the same game again (with possibly different strategy choices), continuing in this manner ad-infinitum. We shall refer to the individual games that make up the sequence as the subgames of the sequence. When playing such a sequence of pseudo-games a strategy for player I would be a rule $P$ that would tell him for every $j$, as a function of his past plays (mixed strategy choices) and losses what mixed strategy to play during the $j$th subgame; a strategy for player II would be a rule $Q$ that would tell him for every $j$, as a function of his own, and his opponent's past plays and losses, what mixed strategy $q$ to play during the $j$th subgame of the sequence. We are thus allowing player II to know what plays player I has made, but we are not granting I the same favor. Among the rules $P$ available to player I we define a special class of rules to be called rules constant on intervals. If $x$ is any real number let $\lbrack x\rbrack$ denote the largest integer that is less than or equal to $x$. For every $\alpha > 1$, let $\Pi(\alpha) = (I_1(\alpha), I_2(\alpha), \cdots, I_n(\alpha), \cdots)$ denote the partition on the set I of positive integers defined by the equations: \begin{equation*}\tag{1.3} I_n(\alpha) = \{(\sum^{n-1}_{k=1} \lbrack k^\alpha\rbrack) + 1, (\sum^{n-1}_{k=1}\lbrack k^\alpha\rbrack) + 2, \cdots, \sum^n_{k=1} \lbrack k^\alpha\rbrack\}; n = 1, 2, 3,\cdots.\end{equation*} For example, $I_1(2) = \{1\}, I_2(2) = \{2, 3, 4, 5\}, I_3(2) = \{6, 7, \cdots, 14\}$; etc. We shall refer to $I_n(\alpha)$ as the $n$th interval of the partition $\Pi (\alpha)$. Note that the cardinality of $I_n(\alpha)$ is $\lbrack n^\alpha\rbrack$. Let us suppose that player I is using some rule $P$ that assigns, with probability 1, the same mixed strategy to the $i$th subgame as it does to the $j$th subgame whenever $i$ and $j$ belong to the same interval $I_n(\alpha), n = 1, 2, 3, \cdots$. In this case we say that $P$ is constant on intervals. Thus if we say that player I is to play a certain strategy $p$ during the $n$th interval of a partition $\Pi(\alpha)$, we mean that he is to play $p$ during every subgame whose index belongs to $I_n(\alpha)$. The particular strategy that player I uses in the $n$th interval (a random variable depending on plays and losses occurring prior to the $n$th interval) will be denoted by $p_n$. For $j = 1, 2, 3, \cdots, N, \cdots$ let $X_j$ represent the loss incurred by player I during the $j$th subgame. Note that the sequence $\{X_n\}$ is a discrete stochastic process whose index set is the set I of positive integers and whose law of evolution is determined by the distributions $P_{(a,b)}$ and by the rules $P$ and $Q$ that the players use. The first objective of this paper is to prove: THEOREM. Suppose players I and II are playing a sequence of identical pseudo-games $G$ satisfying (i) and (ii): (i) Player I has $m \geqq 2$ pure strategy choices. (ii) The distributions $P_{(a,b)}$ have uniformly bounded second moments and for each $a \varepsilon A$ and every Borel set $C, P_{(a,\cdot)}(C)$ is $\mathscr{B}$-measurable. Then there exists a class of rules $\{P\}_m$ for player I such that for all rules $Q$ that player II may use we have: $P \varepsilon \{P\}_m \Rightarrow \operatorname{Pr} (\lim \sup_{N\rightarrow\infty} N^{-1} \sum^N_{j=1} X_j \leqq v_G\mid P, Q) = 1.$ We will show, that is, that the player with incomplete information can do as well asymptotically as he could if he had complete information. The members of $\{P\}_m$ will all be constant on intervals. Our second objective will be to seek a strong convergence rate for $N^{-1} \sum^N_{j=1} X_j$. In the course of achieving this goal we will show that a good partition is obtained by setting $\alpha$ equal to $(m + 2)/m$.

In this paper we are concerned with a problem in the Pólya theory of enumeration. Our main result is the determination of the cycle index of a group SH which acts on a set of equivalence classes VN/H. (Let V and N be finite, non-empty sets and let S and H be permutation groups on V and N respectively; VN is the set of injective mappings of N into V; elements f, g ∈ VN are H-equivalent if there exists θ ∈ H such that fθ = g, and VN/H is the set of H-equivalence classes. Any σ ∈ S induces, in a natural way, a permutation τH(σ) of VN/H, and SH is the group of all τH(σ)'s.) This result is used to enumerate classes of structures such as linear graphs, directed graphs, and generalized graphs. A typical consequence of our results is the determination of the cycle structure of the permutation of the subsets of a finite set induced by a permutation of the set.

This paper investigates the structure of block designs with repeated blocks. Let the block design on the parameters b, v, r, k, and λ contain exactly t distinct blocks B1, B2, …, Bt. Let block Bi be repeated exactly ei times and define E =daig [e1,…et]. Then the incidence matrix A of distinct blocks versus varieties satisfies the matrix equation ATEA = (r−λ)I + λJ, where AT is the transpose of A, I is the indentity matrix of order v, and J is the matrix of 1's of order v. We prove that AAT= (r−λ)E-1 +λkrJ−W, where E−1 is the inverse of E, J is the matrix of 1's of order t, and W is a symmetric positive semidefinite matrix of order t and rank t−v. This basic relationship implies the Mann inequality ei⩽bv = rk as well as refinements of the inequalities of Connor.We also study the structure of block designs (and much more general configurations called E-designs) with t in the close vicinity of v. We prove, for example, that there does not exist a block design with t = v + 1. We conclude with the construction of various interesting infinite families of block designs with repeated blocks. Many problems remain unsolved and a number of topics for further study present themselves.

The solution of the Volterra integral equation, \[ ( * )\qquad x(t) = g_1 (t) + \sqrt {t}g_2 (t) + \int _0^t \frac {K(t,s,x(s))} {\sqrt {t - s} } ds, \quad 0 \leqq t \leqq T,\] where $g_1 (t)$, $g_2 (t)$ and $K(t,s,x)$ are smooth functions, can be represented as $x(t) = u(t) + \sqrt {t}v(t) $,$0 \leqq t \leqq T$, where $u(t)$, $v(t)$ are, smooth and satisfy a system of Volterra integral equations. In this paper, numerical schemes for the solution of (*) are suggested which calculate $x(t)$ via $u(t)$, $v(t)$ in a neighborhood of the origin and use (*) on the rest of the interval $0 \leqq t \leqq T$. In this way, methods of arbitrarily high order can be derived. As an example, schemes based on the product integration analogue of Simpson's rule are treated in detail. The schemes are shown to be convergent of order $h^{{7 / 2}} $. Asymptotic error estimates are derived in order to examine the numerical stability of the methods.

In a continuous production process, samples of fixed size are taken at regular intervals of time and a statistic $X_n$ is computed from the $n$th sample, $n = 1,2, \cdots$. In this paper, we study process inspection schemes which stop the production and take corrective action with $N = \text{first} n \geqq 1$ such that $\sum^n_{i=1} c_{n-i} X_i \geqq h$, where $h$ is a preassigned constant and $c_0 \geqq c_1 \geqq \cdots \geqq c_{k-1} > 0 = c_k = c_{k+1} = \cdots$ is a suitably chosen sequence of weights. The average run length of such procedures is examined, and in the normal case, numerical comparisons with the average run length of the usual Shewhart Chart are given. In connection with the normal case, the first passage times of more general Gaussian sequences are studied and an asymptotic theorem is obtained. The first passage time $N$ for more general weighted sums, where the sequence $(c_n)$ is not assumed to be eventually zero but is assumed to be at least square summable, is also considered.

In his book “Structure of Rings” [7, p. 231 Professor Jacobson raised the following open question: “What are the conditions on a finite dimensional Lie algebra L over a field K that insure that its universal enveloping algebra U(L) is primitive ?” [Since U(L) h as an anti-automorphism the notions left and right primitive are the same for U(L).] If R is of characteristic p f 0, then U(L) cannot be primitive unless L = 0 [7, p. 2551. Th ere f ore we may assume from now on that L is a nonzero finite dimensional Lie algebra over a field Fz of characteristic zero. For each linear functional f EL* we denote by L[f] the set of all x EL such that f (Ex) = 0 for all E in the algebraic hull of ad L C End L. Clearly L[f] is a Lie subalgebra of L containing the center Z(L) of L. The aim of this paper is to prove the following. THEOREM. If U(L) is primitive then L[f] = 0 foT some f EL*. Moreover, the converse holds ifL is solvable and k is algebraically closed. If we denote by D(L) the division ring of quotients of U(L), Z(D(L)) its center, we shall prove that the condition that Llf] = 0 for some f EL* is equivalent with Z(D(L)) = k (which f orces the centers of both L and U(L) to be trivial). In particular, U(L) cannot be primitive if L is either nilpotent or semi-simple. Finally, we shall give some examples of Lie algebras (of which one is not solvable) that do have a primitive universal enveloping algebra.

In this paper, we study weighted sums $\sum^n_{i=1} c_{n-i} X_i$ of i.i.d. zero-mean random variables $X_1, X_2, \cdots$, under the condition that the sequence $(c_n)$ is square summable. It is proved that such weighted sums are, with probability 1, of smaller order than $n^{1/\alpha}$ (respectively $\log n$, etc.) $\operatorname{iff} E|X_1|^\alpha < \infty$ (respectively $Ee^{t|X_1|} < \infty$ for all $t < \infty$, etc.). Certain analogs of the law of the iterated logarithm for such weighted sums are also obtained.

This paper develops, for a Markov chain $\{X_n\}$ on a general space $(\mathscr{X}, \mathscr{F})$ with $n$-step transition probabilities $P^n(x, A), x \in \mathscr{X}, A \in \mathscr{F}$, a theory analogous to that of Vere-Jones for Markov chains on the integers. If the chain is $\phi$-irreducible there is a partition $\mathscr{K}$ of $\mathscr{X}$ such that $\phi$-almost all of the power series $G_z(x, A) = \sum_n P^n(x, A)z^n$ have a common radius of convergence $R$ for $A$ in any element of $\mathscr{K}$, and they all diverge ($R$-recurrence) or all converge ($R$-transience) for $z = R$. The $R$-recurrent case is then investigated, and it is shown that there exist essentially unique non-zero solutions $Q, f$ to the $R$-subinvariant equations $Q \geqq RQP$ and $f \geqq RPf$, and that $Q$ and $f$ satisfy these inequalities with equality: a relationship between $Q$ and $f$ and first-entrance probabilities is also established. Further, if $\{X_n\}$ is aperiodic, $\lim_{n\rightarrow\infty} R^nP^n(x, A) = f(x)Q(A)/\int_\mathscr{X} f(y)Q(dy)$ for almost all $x \in \mathscr{X}$ and $A$ in any element of a second partition. The methods used are probabilistic and depend mainly on generating function techniques: it is pointed out that these techniques do not depend on the substochasticity of the transition probabilities, and hence the results are true in a much wider context.

Let $\{\xi_k: k \geqq 1\}$ be a sequence of independent, identically distributed random variables with $E\{\xi_1\} = 0$ and $E\{\xi_1^2\} = \sigma^2, 0 < \sigma^2 < \infty$. Form the random walk $\{S_n: n \geqq 0\}$ by setting $S_0 = 0, S_n = \xi_1 + \cdots + \xi_n, n \geqq 1$. Let $T$ denote the hitting time of the set $(-\infty, 0\rbrack$ by the random walk. The main result in this paper is a functional central limit theorem for the random functions $S_{\lbrack nt \rbrack}/\sigma n^{\frac{1}{2}}, 0 \leqq t \leqq 1$, conditional on $T > n$. The limit process, $W^+$, is identified in terms of standard Brownian motion. Similar results are obtained for random partial sums and renewal processes. Finally, in the case where $E\{\xi_1\} = \mu > 0$, it is shown that the conditional (on $T > n$) and unconditional weak limit for $(S_{\lbrack nt\rbrack} - \mu nt)/\sigma n^{\frac{1}{2}}$ is the same, namely, Brownian motion.

The linear least squares problem of minimizing ||Ax~ - b~||_(2) where A is an m X n matrix, m >= n, may be solved using the singular value decomposition in approximately 2mn^(3) + 4n^(3) multiplications. In this paper the problem of solving ||A'x~ - b~||_(2) is considered where A' results from deleting or adding a column to A. This might occur when a change is made in the model of a process. Instead of computing the singular value decomposition of A' from scratch, the singular value decomposition of A is updated. Since the updating require about 6n^(3) multiplications the algorithms are useful when m >> n. The problem of recalculation some or all of the singular values of a matrix A', which is obtained by deleting or adding a row or a column from a matrix A, whose singular value decomposition is known, is also studied.

Summary It was proved by Ahlswede (1971) that codes whose codewords form a group or even a linear space do not achieve Shannon's capacity for discrete memoryless channels even if the decoding procedure is arbitrary. Sharper results were obtained in Part I of this paper. For practical purposes, one is interested not only in codes which allow a short encoding procedure but also an efficient decoding procedure. Linear codes—the codewords form a linear space and the decoding is done by coset leader decoding — have a fairly efficient decoding procedure. But in order to achieve high rates the following slight generalization turns out to be very useful: We allow the encoder to use a coset of a linear space as a set of codewords. We call these codes shifted linear codes or coset codes. They were implicitly used by Dobrushin (1963) . This new code concept has all the advantages of the previous one with respect to encoding and decoding efficiency and enables us to achieve positive rate on discrete memoryless channels whenever Shannon's channel capacity is positive and the length of the alphabet is less or equal to 5 (Theorem 3.1.1). (The result holds very likely also for all alphabets with a length a = ps, p prime, s positive integer). A disadvantage of the concepts of linear codes and of shifted linear codes is that they can be defined only for alphabets whose length is a prime power. In order to overcome this difficulty, we introduce generalized shifted linear codes. With these codes we can achieve a positive rate on arbitrary discrete memoryless channels if Shannon's capacity is positive (Theorem 3.2.1)

(1.1) | ~~~~~~~x(t)(p(t) dt, where x(t) is a variable function and (p(t) is a given function. However, if the domain of variation of x(t) is limited to the class of nondecreasing functions, then Schwarz's inequality does not give the least upper bound unless sp(t) itself is effectively a nondecreasing function, because the equality holds only if x(t) is effectively proportional to .p(t). In the present paper, we shall derive a modified Schwarz inequality (1.2) f X(t) f (t) dt < { x(t) dt} { 0f (t)2 dt}, where@p(t) is a nondecreasing function closely related to s(t). It holds for any nondecreasing function x(t) and for any function So(t) in a certain wide class, the equality being satisfied if x(t) = A@p(t) holds with nonnegative constant coefficient A almost everywhere. The relation between So(t) and So(t) is most simply stated by means of the concept of the "greatest convex minorant," whose definition and some of whose properties we shall state in the next section. The inequality (1.2) can profitably be generalized to (3.8), which reduces to (1.2) if b(t) is absolutely continuous and V'(t) = Sp(t). 2. Greatest convex minorant. See for instance ([2] p. 440) and ([3] pp. 91, 94). For a given function 41(t) in a closed interval [a, b], we consider the supremum of all convex functions dominated by 4P(t) in the whole interval. (A convex function

Let $X_1, X_2, \ldots, X_N$ be independent identically distributed random variables with common continuous distribution function $F$. Designate by $\mathscr{J}$ a nonempty set of subsets of the integers $\{ 1, 2,\ldots, N\}$ and by $\mathscr{Y} = \mathscr{Y}(\mathscr{J})$ the mapping which assigns to each set $I \in \mathscr{J}, I = \{t_1, t_2, \ldots, t_k\}$ the partial sum $\sum{t_j \in I}X_{t_j}$. Define the random variable $N = N(\mathscr{J})$ as the number of positive sums in the range of $\mathscr{Y}. N(\mathscr{J})$ has been shown to be distribution free when $F$ is the distribution function of a symmetric random variable if $\mathscr{J} = \{1,2, \ldots, N\}$ or $\mathscr{J} = \text{power set of} \{1,2, \ldots, N\}$. Several other nontrivial examples of this phenomenon have been discovered--all by different methods. This paper presents a unified method that derives all previously known results, provides a constructive method for obtaining infinitely many essentially different sets $\mathscr{J}$ with this property, and finally provides a powerful necessary condition on any such set $\mathscr{J}$ that yields a complete characterization of those sets $\mathscr{J}$ for which $N(\mathscr{J})$ is distribution free and $\mathscr{J}$ contains all $k$ element subsets of $\{1,2, \ldots, N\}$ where $k = 2,3, \ldots, N - 1$.

1. Introduction and summary. In this note, we give simpler proofs of results obtained, regarding the necessary conditions for existence of certain unsymmetrical PBIB designs having group divisible, triangular and Li association schemes, in [5]. We also give simpler proofs of the necessary conditions for the existence of affine a-resolvable GD(m, n), T(n), Li(s) and BIB designs obtained in [6]. We follow the notation of these two papers throughout this note. We finally obtain necessary conditions for the dual of a design D, to be a specified design E. 2. Gramians of the rational characteristic vectors of N'N in terms of the gramians of rational characteristic vectors of NN'. Let 00 = rk, 01 , 02 , ... , Os be the distinct rational characteristic roots of NN', where N is the incidence matrix of the design defined in the usual manner and N' is its transpose, with respective multiplicities ao = 1, a, , a2, ***, -a, and zero be a characteristic root with multiplicity ,B. We shall put (3 = 0 if NN' is non singular and the results of this note still hold true. Obviously 1 + ZE=i=, ai + ( = v. Then, the characteristic roots of N'N are 00, 01, 02, * *X, 0 with respective. multiplici

Here sign (M t l... i r) denotes the usual Hirzebruch signature. (Note that our definition differs slightly from the one of W. C. Hsiang [6] by the presence of the factors 2.) It is easy to see that (*) is independent of the choice of basis. Novikov conjectured that the expression (*) is a homotopy invariant of the manifold X and provided evidence [11] in favor of this conjecture. Rohlin [14] has obtained further partial results. The proof in general has been obtained by W. C. HsiangFarrell [6] and Kasparov [7] using nonsimply connected surgery. One of the results of this paper is a new proof of Novikov's conjecture based on a completely different approach. For any Kahler manifold X there is an associated complex torus Pic (X) whose points are the isomorphism classes of holomorphic line bundles o n ! which are topologically trivial. Let Lp denote the holomorphic line bundle corresponding to p e Pic (X). Then there is a holomorphic line bundle L over X x Pic (X) such that for a given p € Pic (X), the restriction L\X x {p} is isomorphic to Lp. (See [8].) Let AT*X be the p-th exterior power of the holomorphic cotangent bundle of X, and let O(A*T*X®L) be the sheaf of holomorphic sections of ΛT*X(g)L

Let $X_1, X_2, \cdots, X_n, \cdots$ be a sequence of independent, identically distributed random variables with common distribution function $F$. Let $Z_n = \max \{X_1, X_2, \cdots X_n\}$. Conditions for the stability and relative stability of such sequences with the various modes of convergence have been given by Geffroy [3], and Barndorff-Nielsen [1]. The principal result of this paper is Theorem 2.1, which is an analogue for maxima of the law of the iterated logarithm for sums (Loeve [6] pages 260-1). In Section 3, it is indicated that the theorem is satisfied by a wide class of distributions, and specific forms are given for the normal and exponential distributions.

We are given a set of $N$ responses $Y_t$ which have arisen from a nonlinear regression model \begin{equation*}\tag{(1.1)}Y_t = f(x_t, \theta) + e_t; \quad t = 1, 2, \cdots, N.\end{equation*} Here $x_t$ denotes the $t$th fixed input vector of $k$ elements giving rise to $Y_t$, whilst $\theta$ is an $m$-element unknown parameter vector with elements $\theta_i$ and the $e_t$ are a set of $N$ independent error residuals from $N(0, \sigma^2)$ with $\sigma^2$ unknown. The expectations of the $Y_t$, are therefore the functions $f(x_t, \theta)$ which will be assumed to satisfy certain regularity conditions. The problem is to estimate $\theta$ notably by least squares. In this paper we shall develop an iterative method of solution of the least squares equations which has the following properties: (a) the computational procedure is convergent for finite $N$; (b) the resulting estimators are asymptotically $100{\tt\#}$ efficient as $N \rightarrow \infty$. In Sections 2-4 we give a survey of our results leaving the mathematical proofs to Sections 5-7 whilst in Section 8 we illustrate our method with an example. Although our theoretical development is oriented towards our specific goals certain results are proved in a somewhat more general form. Some of our theory will be seen to correspond to well known theorems on stochastic limits which have to be reproved because of certain modifications which we require.

1. When a permutation group G on a set Ω is given, a transitive extension G of G is defined to be a transitive permutation group on the set Γ which is a union of Ω and a new point ∞ such that the stabilizer of ∞ in G1 is isomorphic to G as a permutation group on Ω. The purpose of this paper is to prove that many known simple groups which can be represented as doubly transitive groups admit no transitive extension. Precise statement is found in Theorem 2. For example, the simple groups discovered by Ree [5] do not admit transitive extensions. Theorem 2 includes also a recent result of D. R. Hughes [3] which states that the unitary group U3(q) q>2 does not admit a transitive extension. As an application we prove a recent theorem of H. Nagao [4], which generalizes a theorem of Wielandt on the non-existence of 8-transitive permutation groups not containing the alternating groups under Schreier’s conjecture.

Renyi [19] gives a set of seven postulates which a measure of dependence for a pair of random variables should satisfy. Of the dependence measures considered by Renyi, only Gebelein's [5] maximal correlation, $S_P$, satisfies all seven postulates. Kramer [10] in considering the uncertainty principle in Fourier analysis [11] generalizes the Gebelein maximal correlation to the case of arbitrary pairs of $\sigma$-algebras; and asks whether this generalization is equivalent to Shannon's mutual information, $C_P$, [4, 9, 21] for pairs of $\sigma$-algebras--equivalent in the sense of preserving order. The object of this note is to compare $S_P$ and the two normalizations $C'_P$ and $C"_P$, of $C_P$, as dependence measures for strictly positive probability spaces (which are necessarily generated by random variables). It is found that for such spaces with the proper finiteness restrictions (a) (Thm 5.1) $0 \leqq S_P, C'_P, C"_P \leqq 1$; (b) (Thm 5.2) $S_P = 0 \text{iff} C'_P = 0 \text{iff} C"_P = 0$ iff the random variables are independent; (c) (Thm 5.4) $S_P = 1$ if the two generated algebras have a nontrivial intersection (the conditions are equivalent for finite algebras); $C'_P = 1$ iff one of the random variables is a function of the other; and $C"_P = 1$ iff the random variables are functions of each other; and, consequently, (d) (Thm 5.5) there exist probability spaces for which the dependence measures are not equivalent. The paper is divided into six sections. Section 1 contains the introduction and summary. Section 2 introduces the terminology, notation and preliminaries. Section 3 treats $S_P$ and the Renyi postulates. In Section 4, the basic Shannon-Feinstein-Khinchin mutual information is extended to strictly positive measure spaces, not necessarily finite. The comparison of the dependence measures and postulate modifications are given in Section 5. Finally, in Section 6 some extensions and open problems are mentioned.

Orthogonal arrays can be regarded as natural generalizations of orthogonal Latin squares, and are useful in various problems of experimental design. In this paper the known upper bounds for the maximum possible number of constraints for arrays of strength 2 and 3 have been improved, and certain methods for constructing these arrays have been given.

Let (W, F, P) be a probability space with points ω ∊ W and let (y n , F n ), n = 1, 2, …, be an integrable stochastic sequence: y n is a sequence of random variables, F n is a sequence of σ-algebras with F n ⊂ F n +1 ⊂ F, y n is measurable with respect to and F n , and E(yn) exists, –∞ ≦ E(y n ) ≦ ∞. A random variable s = s(ω) with positive integer values is a sampling variable if {s ≦ n} ∊ F n and {s < ∞} = W. (We denote by {…} the set of all ω satisfying the relation in braces, and understand equalities and inequalities to hold up to sets of P-measure 0.) We shall be concerned with the problem of finding, if it exists, a sampling variable s which maximizes E(y s ).

Let $(\Omega, \mathscr{F}, P)$ be a probability space, $\{X_n: n \geqq 1\}$ an inhomogeneous Markov chain assuming a finite number of states defined on this space, $E = \{a_1, \cdots, a_s\}$ the set of its states, $p_j^{(n)} = P\{X_n = a_j\}, p^{(k, n)}_{ij} = P\{X_n = a_j\mid X_k = a_i\}$ for $n = 2,3, \cdots, n > k, a_i, a_j \in E, \{f_n: n \geqq 1\}$ a sequence of real valued functions defined on $E$ and $S_n = f_1(X_1) + \cdots + f_n(X_n)$. To study the Markov chains which are not subjected to "asymptotic independent" restrictions, the author proposes the coefficients $a_{k,n} = \max'_{i\in\{1, \cdots, s\}} \sum^s_{j=1} (pj^{(n)} - p^{(k,n)}_{ij})^+ (n = 2,3, \cdots, n > k)$ where the dash indicates that the max is taken over those $i$ such that $p_i^{(k)} > 0$. Some limit properties of the sums $\{S_n: n \geqq 1\}$ suitably normed, as the behavior of the series of random variables and the strong law of large numbers are investigated. In the end some examples are given and it is proved that the arbitrary homogeneous Markov chains satisfy most of the conditions imposed in the paper.

Hotelling and Pabst [1] showed that the rank correlation coefficient had a limiting normal distribution under the equally likely permutations of the hypothesis of independence. Wald and Wolfowitz [2] developed a general theorem of this type, and Noether [3] and Hoeffding [4] have relaxed the conditions used therein. In this paper a vector form of the theorem is proved along the lines used in an example by Wald and Wolfowitz [1] but taking account of the singular cases in which the correlations approach one.

In the above paper [1], Varshamov considers discrete channels with q inputs and q outputs, q being an arbitrary integer.

In an attempt to refine the axiomatic model of a probability space introduced by Kolmogorov [11], Gnendenko and Kolmogorov [5] introduced the concept of a perfect probability measure. The desirability of some sort of refinement has been pointed out by several well known examples [2], [3], [8], which display a certain amount of pathology inherent in Kolmogorov's theory. It is known that if $(X, \mathscr{S}, \mu)$ is a probability space and $\mu$ is perfect, then each of the examples mentioned is ruled out. There have been attempts (e.g., [1], [10]) at characterizing all those measurable spaces $(X, \mathscr{S})$ having the property that every probability measure $\mu$ on $\mathscr{S}$ is perfect. There have also been investigations [12], [13], [14] of the measure-theoretic properties of perfect measures and their relationships to other concepts in measure theory and probability theory. In this paper, we consider mixtures of perfect probability measures and their relationship to regular conditional probabilities. In Section 2, mixtures are defined and some interesting special cases are considered. Section 3 is a brief study of the imbedding of mixtures in a regular conditional probability space. Using known results and some results from Section 2, the perfectness of the underlying probability measure of a regular conditional probability space is characterized. Unless explicit mention is made to the contrary, the notation and terminology of [6] will be used throughout; however, the word "function," used without qualification, will always mean "real-valued function." If $(X, \mathscr{S}, \mu)$ is a probability space, then $\mu$ is called perfect if for every $\mathscr{S}$-measurable function $f$ on $X$ and every set $A$ on the real line for which $f^{-1}(A)$ belongs to $\mathscr{S}$, there is a linear Borel set $B$ contained in $A$ such that $\mu(f^{-1}(A)) = \mu(f^{-1} (B))$. It is known (see [13]): (1) that a measure is perfect if and only if its restriction to every countably-generated sub-sigma-algebra is perfect, and (2) that the restriction to any sub-sigma-algebra of a perfect measure is perfect. Since the following characterization of perfectness will be used frequently in the sequel, we quote it here as a lemma. A proof may be found in [14]. Lemma 1. A measure $\mu$ on a measurable space $(X, \mathscr{S})$ is perfect if and only if for every $\mathscr{S}$-measurable function $f$ on $X$ there is a linear Borel set $B(f)$ contained in $f(X)$ such that $\mu(f^{-1}(B(f))) = \mu(X)$. The following definitions are those of Jirina [9]. Let $(X, \mathscr{S}, \mu)$ be a probability space and let $\mathscr{S}_1$ and $\mathscr{S}_2$ be sub-sigma-algebras of $\mathscr{S}$. Any function $\mu(\cdot, \cdot \mid \mathscr{S}_1, \mathscr{S}_2)$ defined on $\mathscr{S}_1 \times X$ will be called a conditional probability (c.p.) if it satisfies: CP1. for fixed $S$ in $\mathscr{S}_1, \mu(S, \cdot \mid \mathscr{S}_1, \mathscr{S}_2)$ is $\mathscr{S}_2$-measurable, and CP2. for every $S$ in $\mathscr{S}_1$, and every $T$ in $\mathscr{S}_2$, $\mu(S \cap T) = \int_T \mu(S_1, x \mid \mathscr{S}_1, \mathscr{S}_2) d(\mu \mid \mathscr{S}_2),$ where $(\mu \mid \mathscr{S}_2)$ is the restriction of $\mu$ to $\mathscr{S}_2$. If the c.p. $\mu(\cdot, \cdot \mid \mathscr{S}_1, \mathscr{S}_2)$ also satisfies: CP3. for each fixed $x$ in $X, \mu(\cdot, x \mid \mathscr{S}_1, \mathscr{S}_2)$ is a probability measure on $\mathscr{S}_1$, then it will be called a regular conditional probability (r.c.p.). It is well known that if $(X, \mathscr{S}, \mu)$ is a probability space, $\mathscr{S}_1$ is any sub-algebra of $\mathscr{S}$, and $\mathscr{S}_2$ is any sub-sigma-algebra of $\mathscr{S}$, then there is a c.p. $\mu(\cdot, \cdot \mid \mathscr{S}_1, \mathscr{S}_2)$. We shall denote by $\mu(\cdot, \cdot \mid \mathscr{S}, \mathscr{S}_2)$ any function satisfying CP1 and CP2, with $\mathscr{S}_1 = \mathscr{S}$.

In a recent paper [1] the author investigated the mean number of steps in random walks in $n$-dimensional domains. The purpose of the present article is to generalize those results by applying similar methods to the study of the moment generating function for the number of steps and of its distribution function. As an application explicit asymptotic expressions for the variance in special cases and estimates for the likelihood of very long walks are obtained. The author wishes to express his thanks to Professor R. Fortet for many helpful discussions. The walks take place in an open bounded domain $B$ of $n$-dimensional Euclidean space $E$ with boundary $C$. A point moves in $E$ according to a given transition probability law $F(y, x)$. Here $x$ and $y$ are points of $E$ with coordinates $x_i, i = 1, 2, \cdots, n$, and $y_i, i = 1, 2, \cdots, n$, and $F(y, x)$ is the probability that a jump known to start at $x$ end at a point all of whose coordinates are less than the corresponding ones of $y$. The function $F(y, x)$ is a distribution function with respect to $y$, and it is assumed to be Borel measurable with respect to all variables. Let $N = N_x$ be the number of steps in a random walk that begins at a point $x$ of $B$ and ends with the step on which the moving point leaves $B$ for the first time. If the probability of the moving point eventually leaving $B$ is equal to one, then $N$ is a random variable. It is called the duration of the walk. It is useful to extend the definition of $N$ by setting $N_x = 0,\quad x \varepsilon E - B$.

Let $\{X_i\}$ be a sequence of independent random variables with the same distribution function $F(x) = \mathrm{P r}\{X_i \leqq x\}$. Let $F(M_p) = p, 0 < p < 1$. Suppose $F$ has two derivatives in a neighborhood of $M_p, F"(x)$ is bounded there and $F'(M_p)$ is positive. Let $Y_{p,n}$ be a sample $p$-quantile based on $X_1, \cdots, X_n$. Let $nG_n(x)$ be the number of $X_i$'s among $(X_1, \cdots, X_n)$ which are $> x$. Bahadur (1966) has proved \begin{equation*}\tag{1}Y_{p,n} = M_p + \lbrack G_n(M_p) - (1 - p)\rbrack/F'(M_p) + R_n\end{equation*} where the remainder term $R_n$ becomes negligible as $n \rightarrow \infty$. More precisely, he has shown $R_n = O(n^{-\frac{3}{4}} \log n)$ a.s. as $n \rightarrow \infty$. The best result of this type is due to Kiefer (1967) who has calculated the exact order of $R_n$. Sen (1968) has extended Bahadur's result to random variables which are neither independent nor identically distributed. We shall give a new and much simpler proof of a weaker version of Bahadur's result which suffices for many statistical applications. Our proof involves fewer assumptions than Bahadur's. For arbitrary $p_n$ let $M_{p_n}$ be defined as $M_p + (p_n - p)/F'(M_p)$. Consider \begin{equation*}\tag{2}Y_{p_n,n} = M_{p_n} + \lbrack G_n(M_p) - (1 - p)\rbrack/F'(M_p) + R_n\end{equation*} where $Y_{p_n,n}$ is a sample $p_n$-quantile. In Section 2 we have proved the following result about $R_n$. THEOREM 1. Suppose $F'(M_p)$ exists and is strictly positive and $p_n - p = O(1/n^{\frac{1}{2}})$. Then $R_n$ as defined in (2) (and, a fortiori, $R_n$ as defined in (1) satisfies \begin{equation*}\tag{3}n^{\frac{1}{2}} R_n \rightarrow 0 \text{in probability}.\end{equation*} (After writing this paper the author discovered that the result for $p_n = p$ is stated without proof in Chernoff et al (1967).) It is easy to extend this result as in Sen (1968). An outline is sketched in one of the remarks. Once again it is possible to achieve some economy in assumptions. The representation (1) is not new. Its use in deriving the asymptotic moments of $Y_{p,n}$ goes back to Karl Pearson. See, for example, (1) in Hojo (1931). But the formulation therein is very imprecise and lacks a rigorous justification. We next consider an application of Theorem 1. Let $\bar{X}_n = (\sum^n_1 X_i)/n$ and $P_n =$ proportion of $X_i$'s above $\bar{X}_n$. David (1962) proved the asymptotic normality of $P_n$ when $F$ is a normal distribution function. Using the same elegant trick, Mustafi (1968) has proved a similar result for bivariate normal distributions. We shall extend these results considerably by providing alternative proofs based on Theorem 1, which dispense with the normality assumption on F. Moreover, in our proof we may consider--though we shall not do so for purposes of simplicity--instead of the sample mean $\bar{X}_n$ an $U$-statistic to which the central limit theorem of Hoeffding (1948) applies.

A hypothesis often made about a sequence of real-valued r.v. (random variables), $\{X_n, n = 0, \pm 1, \pm 2, \cdots\}$ is that there exist certain real constants $\alpha_1, \alpha_2, \cdots, \alpha_k$ such that if we write \begin{equation*}\tag{1} Y_n = X_n + \alpha_1X_{n-1} + \cdots + \alpha_kX_{n-k},\end{equation*} then $\{Y_n\}$ is a sequence of independent r.v. Now, very often in practice, the observed sequence $\{X_n\}$ consists in observations made at equidistant $t$-points on a stochastic process with a continuous parameter $t$. Restricting our attention to the case $k = 1$, we then have a r.f. (random function) $X(t)$, defined for all $t$ in an interval, with the following property: There exist a value of $t (t_0$, say), and $h > 0$, and a real number $\alpha$ such that a hypothesis of the type mentioned is satisfied by the sequence $\{Y(t_0, h; n), n = 0, \pm1, \pm2, \cdots\}$, where \begin{equation*}\tag{2} Y(t_0, h; n) = X(t_0 + nh) - \alpha X(t_0 + \lbrack n - 1\rbrack h).\end{equation*} But if such a hypothesis is true for one value of $h$, it is not necessarily so for some other value; and we have to make the additional assumption that the particular length of the $t$-intervals with which we are concerned is precisely the one for which the hypothesis holds. This assumption may not be reasonable in every case, Instead we may wish to work with a hypothesis similar to the above, but which holds for all positive $h$ in some interval. In this paper, we investigate the existence and form of random functions satisfying a hypothesis of this type. Section 1 contains a statement of the problem and some simple results. It turns out that any random function possessing the required property can be expressed as the product of an exponential function of $t$ and a r.f. with independent increments. Section 2 deals with the limit in distribution of a sequence of Stieltjes approximating sums involving a r.f. with independent increments. Finally, in Section 3, these results are applied to the problem under investigation, and further possibilities are investigated. It must be noted that, in this investigation, we are concerned only with results in distribution. That is to say, we are dealing throughout only with parametric families of probability laws and talking in terms of r.f. merely for convenience.

The question whether a system of n — 1 real algebraic numbers (n = 2, 3, •) chosen from an algebraic field of degree not higher than n9 yields periodicity by Jacobi's Algorithm is still as open and challenging as hundred years ago. The present paper gives an affirmative answer to this problem in the following case: let K(w) be an algebraic number field generated by w = (Dn — d: m)ί/n, where m, n, d, D are natural numbers satisfying the conditions m^ 1, n έ 3, d | D, 1 ^ d ^ D/2(n — 1). Then n — 1 numbers can be chosen from K(w), so that their Jacobi Algorithm becomes purely periodic. The length of the period equals n2 (or n, if d = m = 1). This is the longest period of a periodic Jacobi Algorithm ever known. In three corollaries the following special cases are investigated