Mean values and differential equations

We show that the well-known equivalence between the mean-value theorem and harmonicity extends to arbitrary measures of compact support: a continuous function satisfies the generalized mean-value condition (1) with respect to a given measure if and only if it is annihilated by a certain system of homogeneous linear partial differential operators with constant coefficients determined by the measure. Extensions of this result are obtained, primarily in the direction of replacing systems of differential equations by a single equation. Research and preparation supported in part by NSF GP 28970.     

正态定限（Orthant）概率

本文采用不同以往的方法；对正态定限（Ｏｒｔｈａｎｔ）概率积分施行线性变换与极坐标变换；得到了一个新的递推公式，使积分重数至少降低了３重；并推导了四维正态定限概率的表达式，这对进行数值计算是十分有意义的．     

On the Lagrangian Katz family of distributions as a claim frequency model

The Panjer (Katz) family of distributions is defined by a particular first-order recursion which is built on the basis of two parameters. It is known to characterize the Poisson, negative binomial and binomial distributions. In insurance, its main usefulness is to yield a simple recursive algorithm for the aggregate claims distribution. The present paper is concerned with the more general Lagrangian Katz family of distributions. That family satisfies an extended recursion which now depends on three parameters. To begin with, this recursion is derived through a certain first-crossing problem and two applications in risk theory are described. The distributions covered by the recursion are then identified as the generalized Poisson, generalized negative binomial and binomial distributions. A few other properties of the family are pointed out, including the index of dispersion, an extended Panjer algorithm for compound sums and the asymptotic tail behaviour. Finally, the relevance of the family is illustrated with several data sets on the frequency of car accidents.     

Decoupling inequalities and some mean-value theorems

The purpose of this paper is to present some further applications of the general decoupling theory from [B-D] and [B-D2] to certain diophantine issues. In particular, we consider mean value estimates relevant to the Bombieri- Iwaniec approach to exponential sums and arising in the work of Robert and Sargos [R-S]. Our main input is a new mean-value theorem.     

Hybrid mean value on the difference between an integer and its inverse modulo q

The main purpose of this paper is to study the asymptotic property of one class of number-theoretic functions and give a sharp hybrid mean-value formula by using the generalized Bernoulli numbers, Gauss sums and the mean-value theorems of Dirichlet L-functions.     

A family of the Cauchy type mean-value theorems

The Cauchy type mean-value theorems for the Riemann-Liouville fractional derivative are deduced here from known mean-value theorems of the Lagrange type. A general method for deducing these Cauchy type formulas is extracted. Two Cauchy type formulas are then deduced without a priori knowledge about the Lagrange type mean-value theorems.     

On list primitive recursion and the complexity of computinginf

We present a primitive recursive programinf_with_lists computing the minimum of two natural numbersn andp (written in unary notation) and using primitive recursion on lists. This program has at first sight the required property of visiting simultaneously its inputs, so it is a counterexample to a theorem showing that such a program cannot be written in the language of primitive recursion on natural numbers, in the more general framework of primitive recursion on term algebras. However, its complexity is at leastinf(n,p)² so it does not implement the algorithm we have in mind to computeinf(n,p).     

A mathematical model of a flexible manufacturing system with limited in-process inventory

This paper describes a computationally simple, asymptotic model of a flexible job shop, especially designed for estimating the influence of limited in-process inventory level on the production rate. Its main features make it very similar to the one by Solberg. While Solberg's model consists of a closed queuing network, we propose an open queuing network with a limited amount of inprocess customers; a single customer class is assumed, the various actual processing routes being accounted for by routing probabilities. For such a queuing network, the product form of state probabilities is valid, and the normalization constant can be very simply obtained by a convolution algorithm, close to the one used by Solberg. Various performance indices are calculated, regarding the job shop behaviour over a long period of time. Comparison of analytical results of the model and simulation results are provided in order to estimate the amount of error introduced by assuming exponentially distributed processing times and Poisson inputs in the mathematical representation. Simulations were carried out in FORTRAN-based SLAM language.     

Analysis of a class of dynamic programming models for multi-stage uncertain systems

Uncertainty theory is a new branch of mathematics concerned with the analysis of subjective indeterminacy. This paper deals with the optimal control problem for a multi-stage dynamic system in an indeterminate environment. Firstly, we formulate a practical uncertain control model based on the critical value criterion and present recursion equations for this model based on Bellman’s Principle. A special linear model is shown to illustrate how the recursion equations operate to obtain the analytical solution. Furthermore, we demonstrate a hybrid intelligent algorithm to evaluate and approximate the optimal solutions of more general cases. Finally, a discrete version of the production-inventory problem is discussed and numerically analyzed to illuminate the effectiveness of the methodology.     

On the internal path length of d‐dimensional quad trees

It is proved that the internal path length of a d‐dimensional quad tree after normalization converges in distribution. The limiting distribution is characterized as a fixed point of a random affine operator. We obtain convergence of all moments and of the Laplace transforms. The moments of the limiting distribution can be evaluated from the recursion and lead to first order asymptotics for the moments of the internal path lengths. The analysis is based on the contraction method. In the final part of the paper we state similar results for general split tree models if the expectation of the path length has a similar expansion as in the case of quad trees. This applies in particular to the m‐ary search trees. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 5: 25–41, 1999     

A block Cholesky-LU-based QR factorization for rectangular matrices

The Householder method provides a stable algorithm to compute the full QR factorization of a general matrix. The standard version of the algorithm uses a sequence of orthogonal reflections to transform the matrix into upper triangular form column by column. In order to exploit (level 3 BLAS or structured matrix) computational advantages for block-partitioned algorithms, we develop a block algorithm for the QR factorization. It is based on a well-known block version of the Householder method which recursively divides a matrix columnwise into two smaller matrices. However, instead of continuing the recursion down to single matrix columns, we introduce a novel way to compute the QR factors in implicit Householder representation for a larger block of several matrix columns, that is, we start the recursion at a block level instead of a single column. Numerical experiments illustrate to what extent the novel approach trades some of the stability of Householder's method for the computational efficiency of block methods.     

Truncation and augmentation of level-independent QBD processes

In the study of quasi-birth-and-death (QBD) processes, the first passage probabilities from states in level one to the boundary level zero are of fundamental importance. These probabilities are organized into a matrix, usually denoted by G.The matrix G is the minimal nonnegative solution of a matrix quadratic equation. If the QBD process is recurrent, then G is stochastic. Otherwise, G is sub-stochastic and the matrix equation has a second solution G_sto, which is stochastic. In this paper, we give a physical interpretation of G_sto in terms of sequences of truncated and augmented QBD processes.As part of the proof of our main result, we derive expressions for the first passage probabilities that a QBD process will hit level k before level zero and vice versa, which are of interest in their own right.The paper concludes with a discussion of the stability of a recursion naturally associated with the matrix equation which defines G and G_sto. In particular, we show that G is a stable equilibrium point of the recursion while G_sto is an unstable equilibrium point if it is different from G.     

非Fuchs型方程的新理论——树级数解的表现定理(Ⅰ)

在微分方程的解析理论中非Fuchs型方程的严格显式解至今并未求得(Poincaré问题),本文提出的新理论首次给出非正则积分的一般求法和显式的精确解. 本法与经典理论的根本不同在于摈弃形式解的假定,从方程本身建立对应关系,应用留数定理自动给出非正则积分的解析结构.它由无收缩部和全、半收缩部组成.前者是通常的递推级数,后者则表为树级数.树级数是类新颖的解析函数,通常的递推级数只是它的特例而已. 本文的目的是建立非正则积分的一般理论,为此需要阐明Poincaré问题(1880T.I.P.333)的实质[1]:无法求出非正则积分的显式.根据以下证明的表现定理, 非正则积分是类新颖的解析函数,其中系数D_nk是方程参数的常项树级数.     

Structure Algorithms for Partially Ordered Isotonic Regression

Abstract

An algorithm for isotonic regression is called a structure algorithm if it searches for a “solution partition”—that is, a class of sets on each of which the isotonic regression is a constant. We discuss structure algorithms for partially ordered isotonic regression. In this article we provide a new class of structure algorithms called the isotonic block class (IBC) type algorithms. One of these is called the isotonic block class with recursion method (IBCR) algorithm, which works for partially ordered isotonic regression. It is a generalization of the pooled adjacent violators algorithm and is simpler than the min-max algorithm. We also give a polynomial time algorithm—the isotonic block class with stratification (IBCS) algorithm for matrix-ordered isotonic regression. We demonstrate the efficiency of our IBCR algorithm by using simulation to estimate the relative frequencies of the numbers of level sets of isotonic regressions on certain two-dimensional grids with the matrix order.     

Approximate analysis of arbitrary configurations of open queueing networks with blocking

An algorithm for analyzing approximately open exponential queueing networks with blocking is presented. The algorithm decomposes a queueing network with blocking into individual queues with revised capacity, and revised arrival and service processes. These individual queues are then analyzed in isolation. Numerical experience with this algorithm is reported for three-node and four-node queueing networks. The approximate results obtained were compared against exact numerical data, and they seem to have an acceptable error level.Supported in part by a grant from CAIP Center, Rutgers University.Supported in part by the National Science Foundation under Grant DCR-85-02540.     

Relative error propagation in the recursive solution of linear recurrence relations

This paper is concerned with the numerical solution of the general initial value problem for linear recurrence relations. An error analysis of direct recursion is given, based on relative rather than absolute error, and a theory of relative stability developed.Miller's algorithm for second order homogeneous relations is extended to more general cases, and the propagation of errors analysed in a similar manner. The practical significance of the theoretical results is indicated by applying them to particular classes of problem.     

Diagonal fixed points in algebraic recursion theory

The relation between least and diagonal fixed points is a well known and completely studied question for a large class of partially ordered models of the lambda calculus and combinatory logic. Here we consider this question in the context of algebraic recursion theory, whose close connection with combinatory logic recently become apparent. We find a comparatively simple and rather weak general condition which suffices to prove the equality of least fixed points with canonical (corresponding to those produced by the Curry combinator in lambda calculus) diagonal fixed points in a class of partially ordered algebras which covers both combinatory spaces of Skordev and operative spaces of Ivanov. Especially, this yields an essential improvement of the axiomatization of recursion theory via combinatory spaces. Supported in part by the Ministry of Education and Science of Republic of Bulgaria, contract No 705     

Maximal independent sets on a grid graph

An independent vertex set of a graph is a set of vertices of the graph in which no two vertices are adjacent, and a maximal independent set is one that is not a proper subset of any other independent set. In this paper we count the number of maximal independent sets of vertices on a complete rectangular grid graph. More precisely, we provide a recursive matrix-relation producing the partition function with respect to the number of vertices. The asymptotic behavior of the maximal hard square entropy constant is also provided. We adapt the state matrix recursion algorithm, recently invented by the author to answer various two-dimensional regular lattice model problems in enumerative combinatorics and statistical mechanics.     

Blocking Probabilities in Mobile Communications Networks with Time-Varying Rates and Redialing Subscribers

Call-blocking probabilities are among the key performance measures in mobile communications networks. For their analysis, mobile networks can be modelled as networks of Erlang loss queues with common capacity restrictions dictated by the allocation of frequencies to the cells of the network. However, due to the time-varying load offered to the cells of such networks, blocking probabilities usually cannot be obtained in closed form. The relation between networks of Erlang loss queues and networks of infinite server queues, for which the time-dependent occupancy distribution is multidimensional Poisson, suggests to use that distribution as approximate distribution for the network of Erlang loss queues. This paper extends this so-called Modified Offered Load (MOL) approximation to networks of Erlang loss queues, and also allows subscribers that find their call blocked to redial to continue their call. For GSM networks operating under Fixed Channel Allocation, it is shown that blocking probabilities are increasing in the redial rates so that the MOL approximation that is most accurate for maximal redial rates turns out to be fairly accurate for the resulting upper bound for blocking probabilities. The accuracy is explicitly evaluated in an application of the results towards blocking probabilities in a hot spot travelling along a road through a GSM network.     

基于马氏链拟合的一种非负变权组合预测算法及其应用

通过马氏链拟合的方法求取一种新的非负时变权组合预测算法公式.主要工作是:一、对组合预测问题以最小误差为准则给出了马氏链的状态和状态概率初步估计;二、用马氏链拟合状态概率分布时变规律,通过约束多元自回归模型导出了一步转移概率阵的LS解;三、给出一种非负时变权组合预测公式并举一应用实例.