Simple and efficient algorithms for computing exact cumulative discrete probabilities and its inverses

Summary  This paper deals with the computation of exact cumulative probabilities of discrete distributions and its inverses. For the computation of cumulative probabilities an efficient and universal algorithm of 15 lines is presented, which can be applied to the most important discrete distributions (e.g. the binomial, the poisson and the hypergeometric distribution). With a slight modification an algorithm of 20 lines is obtained for the calculation of the respective inverse distributions. The accuracy of both algorithms can be specified. Both algorithms are simple, very fast and numerically stable even if the sample size is one billion.     

A modified steepest descent method with applications to maximizing likelihood functions

In maximizing a non-linear function G(), it is well known that the steepest descent method has a slow convergence rate. Here we propose a systematic procedure to obtain a 1–1 transformation on the variables , so that in the space of the transformed variables, the steepest descent method produces the solution faster. The final solution in the original space is obtained by taking the inverse transformation. We apply the procedure in maximizing the likelihood functions of some generalized distributions which are widely used in modeling count data. It was shown that for these distributions, the steepest descent method via transformations produced the solutions very fast. It is also observed that the proposed procedure can be used to expedite the convergence rate of the first derivative based algorithms, such as Polak-Ribiere, Fletcher and Reeves conjugate gradient methods as well.     

Some Truncated Distributions

Long-tailed distributions arise in many areas of the sciences. These distributions, however, suffer from the weakness of not having finite moments of all orders and this weakness has restricted their use. In this note, we introduce truncated versions of five of the most commonly known long-tailed distributions—which possess finite moments of all orders and could therefore be better models. Explicit expressions for the moments are derived for each of the truncated distributions. Several applications are illustrated using real data.     

An investigation of phase-distribution moment-matching algorithms for use in queueing models

Algorithms for matching moments to phase-type distributions are evaluated on the basis of their performance in their intended application, queueing models. The moment-matching algorithms under consideration match two moments to a hyperexponential distribution with balanced means and three moments to a mixture of two Erlang distributions of common order. These algorithms are used to approximate an interarrival-time distribution for a queueing model, and the accuracy of associated performance-measure approximations is then used to evaluate the moment-matching algorithms. Three performance measures are considered, and attention is focussed on the steady-state mean queue length (number in system) of theGI/M/1 queue. Performance-measure approximations are compared to three-moment bounds and performance-measure values arising from hypothetical approximated distributions.     

MM Algorithms for Some Discrete Multivariate Distributions

The MM (minorization–maximization) principle is a versatile tool for constructing optimization algorithms. Every EM algorithm is an MM algorithm but not vice versa. This article derives MM algorithms for maximum likelihood estimation with discrete multivariate distributions such as the Dirichlet-multinomial and Connor–Mosimann distributions, the Neerchal–Morel distribution, the negative-multinomial distribution, certain distributions on partitions, and zero-truncated and zero-inflated distributions. These MM algorithms increase the likelihood at each iteration and reliably converge to the maximum from well-chosen initial values. Because they involve no matrix inversion, the algorithms are especially pertinent to high-dimensional problems. To illustrate the performance of the MM algorithms, we compare them to Newton’s method on data used to classify handwritten digits.     

Computational methods for discrete hidden semi-Markov chains

We propose a computational approach for implementing discrete hidden semi-Markov chains. A discrete hidden semi-Markov chain is composed of a non-observable or hidden process which is a finite semi-Markov chain and a discrete observable process. Hidden semi-Markov chains possess both the flexibility of hidden Markov chains for approximating complex probability distributions and the flexibility of semi-Markov chains for representing temporal structures. Efficient algorithms for computing characteristic distributions organized according to the intensity, interval and counting points of view are described. The proposed computational approach in conjunction with statistical inference algorithms previously proposed makes discrete hidden semi-Markov chains a powerful model for the analysis of samples of non-stationary discrete sequences. Copyright © 1999 John Wiley & Sons, Ltd.     

A space of generalized distributions

In this paper we use a duality method to introduce a new space of generalized distributions. This method is exactly the same introduced by Schwartz for the distribution theory. Our space of generalized distributions contains all the Schwartz distributions and all the multipole series of physicists and is, in a certain sense, the smallest space containing all these series. To The Memory of Laurent Schwartz     

Phase-type distributions for failure times

Phase-type distributions describe the random time taken for a Markov process to reach an absorbing state. In the context of component failure, sequential movement through the transient states (phases) of such a system could describe the ageing process with movement out of these states (absorption) corresponding to failure. Thus, the lifetime of a component is the absorption time and the probability distribution of these times can be written in terms of the solution of a system of differential equations for which there are many convenient computational algorithms. A variety of different distributions is possible by varying the parameters of the process and hazard rates of various shapes can be constructed, allowing different patterns of variation in observed data to be modelled. These distributions are applied to some industrial data-sets and further features of the processes discussed.     

On the Distribution Behaviour of Sequences

This paper presents results concerning those sets of finite Borel measures μ on a locally compact Hausdorff space X with countable topological base which can be represented as the set of limit distributions of some sequence. They arc characterized by being nonanpty, closed, connected and containing only measures μ with μ(X) = 1 (if X is compact) or 0 ≤ μ(X) ≤ 1 (if X is not compact). Any set with this properties can be obtained as the set of limit distributions of a sequence even by rearranging an arbitrarily given sequence which is dense in the sense that the set of accumulation points is the whole space X. The typical case (in the sense of Baire categories) is that a sequence takes as limit distributions all possible measures of this kind. This gives new aspects for the recent theory of maldistribukd sequences.     

Generalized renewal sequences and infinitely divisible lattice distributions

We introduce an increasing set of classes Γ_a (0?α?1) of infinitely divisible (i.d.) distributions on {0,1,2,…}, such that Γ₀ is the set of all compound-geometric distributions and Γ₁ the set of all compound-Poisson distributions, i.e. the set of all i.d. distributions on the non-negative integers. These classes are defined by recursion relations similar to those introduced by Katti [4] for Γ₁ and by Steutel [7] for Γ₀. These relations can be regarded as generalizations of those defining the so-called renewal sequences (cf. [5] and [2]). Several properties of i.d. distributions now appear as special cases of properties of the Γ_a'.     

New versions of the Colombeau algebras

We construct some versions of the Colombeau theory. In particular, we construct the Colombeau algebra generated by harmonic (or polyharmonic) regularizations of distributions connected with a half‐space and by analytic regularizations of distributions connected with an octant. Unlike the standard Colombeau's scheme, our theory has new generalized functions that can be easily represented as weak asymptotics whose coefficients are distributions, i.e., in form of asymptotic distributions . The algebra of asymptotic distributions generated by the linear span of associated homogeneous distributions (in the one‐dimensional case) which we constructed earlier [9] can be embedded as a subalgebra into our version of Colombeau algebra. The representation of distributional products in the form of weak asymptotic series proved very useful in solving problems which arise in the theory of discontinuous solutions of hyperbolic systems of conservation laws [10]–[16], [49] and [50]. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Waiting-time tail probabilities in queues with long-tail service-time distributions

We consider the standardGI/G/1 queue with unlimited waiting room and the first-in first-out service discipline. We investigate the steady-state waiting-time tail probabilitiesP(W>x) when the service-time distribution has a long-tail distribution, i.e., when the service-time distribution fails to have a finite moment generating function. We have developed algorithms for computing the waiting-time distribution by Laplace transform inversion when the Laplace transforms of the interarrival-time and service-time distributions are known. One algorithm, exploiting Pollaczek's classical contourintegral representation of the Laplace transform, does not require that either of these transforms be rational. To facilitate such calculations, we introduce a convenient two-parameter family of long-tail distributions on the positive half line with explicit Laplace transforms. This family is a Pareto mixture of exponential (PME) distributions. These PME distributions have monotone densities and Pareto-like tails, i.e., are of orderx ^–r forr>1. We use this family of long-tail distributions to investigate the quality of approximations based on asymptotics forP(W>x) asx. We show that the asymptotic approximations with these long-tail service-time distributions can be remarkably inaccurate for typicalx values of interest. We also derive multi-term asymptotic expansions for the waiting-time tail probabilities in theM/G/1 queue. Even three terms of this expansion can be remarkably inaccurate for typicalx values of interest. Thus, we evidently must rely on numerical algorithms for determining the waiting-time tail probabilities in this case. When working with service-time data, we suggest using empirical Laplace transforms.     

服务系统中位相型分布的随机比较

本文运用应用概率中的随机占优研究位相型(PH)分布的随机比较问题,具体给出在一阶、二阶随机占优下比较两个离散PH分布或两个连续PH分布的充分条件及充分必要条件。研究表明,比较两个离散PH分布可变性的条件与比较两个连续PH分布可变性的条件不同,在二阶随机占优意义下比较两个连续PH分布的条件与均值无关,而比较两个离散PH分布的条件与均值有关。本文的结果可用于研究PH分布的最小变异系数问题和可变性问题,也可用于研究带有PH到达间隔或PH服务的排队系统中到达过程或服务时间可变性对系统队长或等待时间的影响。     

Compartmental models with phase-type residence-time distributions

Phase-type (PH) probability distributions provide a versatile class of distributions, and are shown to fit naturally into a Markovian compartmental system, where “individuals” or “particles” move between a series of compartments, so that phase-type compartmental residence-time distributions can be incorporated simply by increasing the size of the system. Examples of PH distributions covering a variety of behaviours are given, and an application involving data analysis is included.     

Sparse pseudorandom distributions

The existence of sparse pseudorandom distributions is proved. These are probability distributions concentrated in a very small set of strings, yet it is infeasible for any polynomial-time algorithm to distinguish between truly random coins and coins selected according to these distributions. It is shown that such distributions can be generated by (nonpolynomial) probabilistic algorithms, while probabilistic polynomial-time algorithms cannot even approximate all the pseudorandom distributions. Moreover, we show the existence of evasive pseudorandom distributions which are not only sparse, but also have the property that no polynomial-time algorithm may find an element in their support, except for a negligible probability. All these results are proved independently of any intractability assumption.     

Approximation of aggregate claims distributions by compound poisson distributions

New error bounds are derived for the approximation of aggregate claims distributions by compound Poisson distributions. These approximations can be recommended in most cases in which the normal approximation fails.     

用矩匹配方法计算非线性风险度

矩匹配方法是用来求解非线性风险度(Value at Risk，简称：VaR)的一种普遍性方法，它是先假定样本经验分布服从已知分布族，然后运用矩匹配估计方法估计相应的参数，得到资产回报样本的密度函数，再计算风险度VaR；本采用的Johnson分布族是矩匹配方法的直接应用，并且计算出来的结果与局部Monte．Carlo结果进行了比较。并通过实证分析认为这种方法是一种良好的计算非线性VaR方法。     

An algebraic approach to tempered distributions

A space of pseudoquotients is introduced that is shown to be isomorphic to the space of tempered distributions on RN. The Fourier transform is defined as a map from the space of pseudoquotients to the space of tempered distributions and as a transformation on pseudoquotients.     

Phase-type distributions in stochastic automata networks

Stochastic automata networks (Sans) are high-level formalisms for modeling very large and complex Markov chains in a compact and structured manner. To date, the exponential distribution has been the only distribution used to model the passage of time in the evolution of the different San components. In this paper we show how phase-type distributions may be incorporated into Sans thereby providing the wherewithal by which arbitrary distributions can be used which in turn leads to an improved ability for more accurately modeling numerous real phenomena.     

Marshall and Olkin’s Distributions

A review is provided of the continuous and discrete distributions introduced by the eminent Professors Marshall and Olkin. The topics reviewed include: bivariate geometric distribution, extreme value behavior, bivariate negative binomial distribution, bivariate exponential distribution, concomitants, reliability, distributions of sums and ratios, Ryu’s bivariate exponential distribution, bivariate Pareto distribution and generalized exponential and Weibull distributions. Some hitherto unknown results about these distributions are also mentioned. This is a tribute to the work of Professors Marshall and Olkin.