The problem of optimal stopping in a partially observable Markov chain

The optimal-stopping problem in a partially observable Markov chain is considered, and this is formulated as a Markov decision process. We treat a multiple stopping problem in this paper. Unlike the classical stopping problem, the current state of the chain is not known directly. Information about the current state is always available from an information process. Several properties about the value and the optimal policy are given. For example, if we add another stop action to thek-stop problem, the increment of the value is decreasing ink.The author wishes to thank Professor M. Sakaguchi of Osaka University for his encouragement and guidance. He also thanks the referees for their careful readings and helpful comments.     

Finite dimensional approximation in infinite dimensional mathematical programming

We consider the problem of approximating an optimal solution to a separable, doubly infinite mathematical program (P) with lower staircase structure by solutions to the programs (P(N)) obtained by truncating after the firstN variables andN constraints of (P). Viewing the surplus vector variable associated with theNth constraint as a state, and assuming that all feasible states are eventually reachable from any feasible state, we show that the efficient set of all solutions optimal to all possible feasible surplus states for (P(N)) converges to the set of optimal solutions to (P). A tie-breaking algorithm which selects a nearest-point efficient solution for (P(N)) is shown (for convex programs) to converge to an optimal solution to (P). A stopping rule is provided for discovering a value ofN sufficiently large to guarantee any prespecified level of accuracy. The theory is illustrated by an application to production planning.The work of Robert L. Smith was partially supported by the National Science Foundation under Grant ECS-8700836.     

Ein metrischer Satz derC-Gleichverteilung

A metric theorem onC-uniform distribution will be proved and some applications will be mentioned, e. g. theC-uniform distribution for (in a certain sense) almost all continuously differentiable functions.     

Recursive adaptive control of Markov decision processes with the average reward criterion

We are concerned with Markov decision processes with Borel state and action spaces; the transition law and the reward function depend on anunknown parameter. In this framework, we study therecursive adaptive nonstationary value iteration policy, which is proved to be optimal under thesame conditions usually imposed to obtain the optimality of other well-knownnonrecursive adaptive policies. The results are illustrated by showing the existence of optimal adaptive policies for a class of additive-noise systems with unknown noise distribution.This research was supported in part by the Consejo Nacional de Ciencia y Tecnología under Grants PCEXCNA-050156 and A128CCOEO550, and in part by the Third World Academy of Sciences under Grant TWAS RG MP 898-152.     

<Emphasis Type="Italic">I</Emphasis>-projection onto isotonic cones and its applications to maximum likelihood estimation for log-linear models

A frequently occurring problem is to find a probability vector,p∈D, which minimizes theI-divergence between it and a given probability vector π. This is referred to as theI-projection of π ontoD. Darroch and Ratcliff (1972,Ann. Math. Statist.,43, 1470–1480) gave an algorithm whenD is defined by some linear equalities and in this paper, for simplicity of exposition, we propose an iterative procedure whenD is defined by some linear inequalities. We also discuss the relationship betweenI-projection and the maximum likelihood estimation for multinomial distribution. All of the results can be applied to isotonic cone.     

Ehresmann connection for the canonical foliation on a manifold over a local algebra

For a canonical foliation on a manifoldM ^A over a local algebra, theA-affine horizontal distribution complementary to the leaves, similar to the horizontal distribution of a higher order connection on the fiber bundle ofA-jets, is defined. In the case of a complete manifoldM ^A, theA-affine horizontal distribution is proved to be an Ehresmann connection in the sense of Blumental-Hebda. It is shown that theA-affine horizontal distribution onM ^A exists if and only if the Atiyah class of a certain foliated principal bundle vanishes.Translated fromMatematicheskie Zametki, Vol. 59, No. 2, pp. 303–310, February, 1996.     

Stopping distributions for right processes

Summary LetX be a transient right process for which semipolar sets are polar. We characterize the measures which can arise as the distribution ofX _T withT a non-randomized stopping time.This work was done while the first-named author was visiting the University of California, San DiegoThe second-named author's research is supported in part by NSF grant DMS8721347     

Asymptotics of Damped Periodic Motions with Random Initial Speed

We consider motion on the circle, possibly with friction and external forces, the initial velocity being a large random variable. We prove that under various assumptions the probability law of the stopping position of the motion converges to a distribution depending only on the motion equation. Here the time of stopping is either a constant or the first time instant at which the velocity vanishes, and the initial velocity is of the form αU + β, where U is a fixed random variable and α and/or β tend to infinity.     

On discrete distributions of orderk

Summary This paper gives some results on calculation of probabilities and moments of the discrete distributions of orderk. Further, a new distribution of orderk, which is called the logarithmic series distribution of orderk, is investigated. Finally, we discuss the meaning of theorder of the distributions. The Institute of Statistical Mathematics     

Linear prediction of record values for the two parameter exponential distribution

This paper deals with the problem of predicting thesth record value based on the firstm record values (s>m) when the observations are from the exponential distribution. Various estimates for thesth record value are obtained and their mean square errors are compared.     

Matrices, moments and quadrature II; How to compute the norm of the error in iterative methods

In this paper, we study the numerical computation of the errors in linear systems when using iterative methods. This is done by using methods to obtain bounds or approximations of quadratic formsu ^T A ⁻¹ u whereA is a symmetric positive definite matrix andu is a given vector. Numerical examples are given for the Gauss-Seidel algorithm. Moreover, we show that using a formula for theA-norm of the error from Dahlquist, Golub and Nash [1978] very good bounds of the error can be computed almost for free during the iterations of the conjugate gradient method leading to a reliable stopping criterion. The work of the first author was partially supported by NSF Grant CCR-950539.     

Permutations of the Walsh system that preserve Lebesgue constants

A class of permutations of the Walsh-Paley system that preserve the lebesgue constants and theL ^p -norms of the Dirichlet kernel is distinguished. Thus it is proved, in particular, that Fine’s estimates and calculations of the Lebesgue constants for the Walsh—Paley system hold for the Walsh systems in the enumerations of Walsh and Kaczmarz. A third algorithm for calculating the Lebesgue constants, which is different from those obtained by Fine and which also makes it possible to calculate theL ^p -norms of the Dirichlet kernels, is proposed. It is shown that not all permutations of the Walsh system even within the blocks preserve the Lebesgue constants. The distinguished class of permutations includes theTW-systems of Schipp, which are not, in general, permutations within the blocks. Translated fromMatematicheskie Zametki, Vol. 68, No. 1, pp. 36–48, July, 2000.     

Rates of uniform convergence of extreme order statistics

Summary Bounds for the convergence uniformly over all Borel sets of the largest order statistic as well as of the joint distribution of extremes are established which reveal in which way these rates are determined by the distance of the underlying density from the density of the corresponding generalized Pareto distribution. The results are highlighted by several examples among which there is a bound for the rate at which the joint distribution of thek largest order statistics from a normal distribution converges uniformly to its limit.     

Empirical Bayes detection of a change in distribution

The problem of detection of a change in distribution is considered. Shiryayev (1963, Theory Probab. Appl., 8, pp. 22–46, 247–264 and 402–413; 1978, Optimal Stopping Rules, Springer, New York) solved the problem in a Bayesian framework assuming that the prior on the change point is Geometric (p). Shiryayev showed that the Bayes solution prescribes stopping as soon as the posterior probability of the change having occurred exceeds a fixed level. In this paper, a myopic policy is studied. An empirical Bayes stopping time is investigated for detecting a change in distribution when the prior is not completely known.Research was supported in part by the Natural Sciences and Engineering Research Council of Canada under grant GP 7987.     

A value for games withn players andr alternatives

We study value theory for a class of games called games withn players andr alternatives. In these games, each of then players must choose one and only one of ther alternatives. A linear, efficient value is obtained using three characterizations, two of which are axiomatic. This value yields an a priori evaluation for each player relative to each alternative.     

Analyzing the discrete-timeG (G)/Geo/1 queue using complex contour integration

In this paper, a discrete-time single-server queueing system with an infinite waiting room, referred to as theG ^(G)/Geo/1 model, i.e., a system with general interarrival-time distribution, general arrival bulk-size distribution and geometrical service times, is studied. A method of analysis based on integration along contours in the complex plane is presented. Using this technique, analytical expressions are obtained for the probability generating functions of the system contents at various observation epochs and of the delay and waiting time of an arbitrary customer, assuming a first-come-first-served queueing discipline, under the single restriction that the probability generating function for the interarrival-time distribution be rational. Furthermore, treating several special cases we rediscover a number of well-known results, such as Hunter's result for theG/Geo/1 model. Finally, as an illustration of the generality of the analysis, it is applied to the derivation of the waiting time and the delay of the more generalG ^(G)/G/1 model and the system contents of a multi-server buffer-system with independent arrivals and random output interruptions.Both authors wish to thank the Belgian National Fund for Scientific Research (NFWO) for support of this work.     

Convergence of self-normalized generalizedU-statistics

Conditions are given for almost certain and distribution convergence of self-normalized generalizedU-statistics composed of random variables without particular probabilistic structure. The set of almost certain limit points of some classicalU-statistics is obtained. A variant of theU-statistic involving squares of some of the random variables is also treated. Applications include Martingale differences, stationary sequences, and the classical i.i.d. case where a Marcinkiewicz-Zygmund-type strong law is obtained.     

Improving estimation in speckled imagery

We propose an analytical bias correction for the maximum likelihood estimators of theG ₁ ⁰ distribution. This distribution is a very powerful tool for speckled imagery analysis, since it is capable of describing a wide range of target roughness. We compare the performance of the corrected estimators with the corresponding original version using Monte Carlo simulation. This second-order bias correction leads to estimators which are better from both the bias and mean square error criteria.     

Skorokhod embeddings, minimality and non-centred target distributions

In this paper we consider the Skorokhod embedding problem for target distributions with non-zero mean. In the zero-mean case, uniform integrability provides a natural restriction on the class of embeddings, but this is no longer suitable when the target distribution is not centred. Instead we restrict our class of stopping times to those which are minimal, and we find conditions on the stopping times which are equivalent to minimality. We then apply these results, firstly to the problem of embedding non-centred target distributions in Brownian motion, and secondly to embedding general target laws in a diffusion. We construct an embedding (which reduces to the Azema-Yor embedding in the zero-target mean case) which maximises the law of sup_s≤TB_s among the class of minimal embeddings of a general target distribution μ in Brownian motion. We then construct a minimal embedding of μ in a diffusion X which maximises the law of sup_s≤Th(X_s) for a general function h.     

Error estimates for the combinedh andp versions of the finite element method

Summary In theh-version of the finite element method, convergence is achieved by refining the mesh while keeping the degree of the elements fixed. On the other hand, thep-version keeps the mesh fixed and increases the degree of the elements. In this paper, we prove estimates showing the simultaneous dependence of the order of approximation on both the element degrees and the mesh. In addition, it is shown that a proper design of the mesh and distribution of element degrees lead to a better than polynomial rate of convergence with respect to the number of degrees of freedom, even in the presence of corner singularities. Numerical results comparing theh-version,p-version, and combinedh-p-version for a one dimensional problem are presented.