Perfect Simulation for a Stationary Silo with Absorbing Walls

The objective of this work is to generate random samples of the unique stationary distribution associated to the stochastic model for grain storage in a finite bidimensional silo. The support of this measure is an unbounded and continuous state space and therefore a truncation was necessary to apply the CFTP perfect simulation scheme. The performance of the algorithm was measured by comparing the sample moments to the theoretical ones.     

Perfect simulation and inference for point processes given noisy observations

Summary  The paper is concerned with the exact simulation of an unobserved true point process conditional on a noisy observation. We use dominated coupling from the past (CFTP) on an augmented state space to produce perfect samples of the target marked point process. An optimized coupling of the target chains makes the algorithm considerable faster than with the standard coupling used in dominated CFTP for point processes. The perfect simulations are used for inference and the results are compared to an ordinary Metropolis-Hastings sampler.     

How to couple from the past using a read‐once source of randomness

We give a new method for generating perfectly random samples from the stationary distribution of a Markov chain. The method is related to coupling from the past (CFTP), but only runs the Markov chain forwards in time, and never restarts it at previous times in the past. The method is also related to an idea known as PASTA (Poisson arrivals see time averages) in the operations research literature. Because the new algorithm can be run using a read‐once stream of randomness, we call it read‐once CFTP. The memory and time requirements of read‐once CFTP are on par with the requirements of the usual form of CFTP, and for a variety of applications the requirements may be noticeably less. Some perfect sampling algorithms for point processes are based on an extension of CFTP known as coupling into and from the past; for completeness, we give a read‐once version of coupling into and from the past, but it remains unpractical. For these point process applications, we give an alternative coupling method with which read‐once CFTP may be efficiently used. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 85–113, 2000     

The Equivalence of Ergodicity and Weak Mixing for Infinitely Divisible Processes

The equivalence of ergodicity and weak mixing for general infinitely divisible processes is proven. Using this result and [9], simple conditions for ergodicity of infinitely divisible processes are derived. The notion of codifference for infinitely divisible processes is investigated, it plays the crucial role in the proofs but it may be also of independent interest.     

ALGORITHMS FOR IMPLEMENTATION OF GENERAL LIMIT REPRESENTATIONS OF GENERALIZED INVERSES

1. Introduction and PreliminariesThe set of all m x n comPlex matrices of rank r is denoted by cy". By I we denote anappropriate ideniity matrix. Also, n(A) denotes the trace of a square matriX A. By n(A) andN(A) are denoted the range and the null space of A, respectively Finally ad(A) and det(A)denote the adoint of the matris A and the determinant of A, respectivelyFOr any matrix A E crxn consider the following equations in X:(1) AXA=A, (2) XAX=X, (3) (AX)*=AX, (4) (XA)*=XAand…     

分装式流水作业加工模型的性质及启发式算法研究

分装式流水作业(简记为TMF)加工模型是从生产实践中提炼出的新型的排序模型。由于文献[1][2]中已经证明该问题在一般情况下是NP-完全问题,没有多项式时间算法。在这篇论文中进一步讨论了该加工模型的性质,并提出了它的启发式算法以及启发式算法在最坏情况下的性能比的上界。     

拟生灭过程几种遍历性的判别准则(Ⅱ)

本文是文[7]的继续,研究了连续时间拟生灭过程,给出了一类连续时间拟生灭过程l-遍历和几何遍历行之有效的判别准则,并证明其不可能是多项式一致遍历和强遍历的.     

Central limit theorems for supercritical branching Markov processes

In this paper we establish spatial central limit theorems for a large class of supercritical branching Markov processes with general spatial-dependent branching mechanisms. These are generalizations of the spatial central limit theorems proved in [1] for branching OU processes with binary branching mechanisms. Compared with the results of [1], our central limit theorems are more satisfactory in the sense that the normal random variables in our theorems are non-degenerate.     

Tuning distributed control algorithms for optimal functioning

In this paper, we present a model which characterizes distributed computing algorithms. The goals of this model are to offer an abstract representation of asynchronous and heterogeneous distributed systems, to present a mechanism for specifying externally observable behaviours of distributed processes and to provide rules for combining these processes into networks with desired properties (good functioning, fairness...). Once these good properties are found, the determination of the optimal rules are studied.Subsequently, the model is applied to three classical distributed computing problems: namely the dining philosophers problem, the mutual exclusion problem and the deadlock problem, (generalizing results of our previous publications [1], [2]). The property of fairness has a special position that we discuss.     

Speeding up the FMMR perfect sampling algorithm: A case study revisited

In a previous paper by the second author, two Markov chain Monte Carlo perfect sampling algorithms—one called coupling from the past (CFTP) and the other (FMMR) based on rejection sampling—are compared using as a case study the move‐to‐front (MTF) self‐organizing list chain. Here we revisit that case study and, in particular, exploit the dependence of FMMR on the user‐chosen initial state. We give a stochastic monotonicity result for the running time of FMMR applied to MTF and thus identify the initial state that gives the stochastically smallest running time; by contrast, the initial state used in the previous study gives the stochastically largest running time. By changing from worst choice to best choice of initial state we achieve remarkable speedup of FMMR for MTF; for example, we reduce the running time (as measured in Markov chain steps) from exponential in the length n of the list nearly down to n when the items in the list are requested according to a geometric distribution. For this same example, the running time for CFTP grows exponentially in n. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

A fast minimal residual algorithm for shifted unitary matrices

A new iterative scheme is described for the solution of large linear systems of equations with a matrix of the form A = ρU + ζI, where ρ and ζ are constants, U is a unitary matrix and I is the identity matrix. We show that for such matrices a Krylov subspace basis can be generated by recursion formulas with few terms. This leads to a minimal residual algorithm that requires little storage and makes it possible to determine each iterate with fairly little arithmetic work. This algorithm provides a model for iterative methods for non-Hermitian linear systems of equations, in a similar way to the conjugate gradient and conjugate residual algorithms. Our iterative scheme illustrates that results by Faber and Manteuffel [3,4] on the existence of conjugate gradient algorithms with short recurrence relations, and related results by Joubert and Young [13], can be extended.     

Exploring the Spectra of Some Classes of Singular Integral Operators with Symbolic Computation

Spectral theory has many applications in several main scientific research areas (structural mechanics, aeronautics, quantum mechanics, ecology, probability theory, electrical engineering, among others) and the importance of its study is globally acknowledged. In recent years, several software applications were made available to the general public with extensive capabilities of symbolic computation. These applications, known as computer algebra systems (CAS), allow to delegate to a computer all, or a significant part, of the symbolic calculations present in many mathematical algorithms. In our work we use the CAS Mathematica to implement for the first time on a computer analytical algorithms developed by us and others within the Operator Theory. The main goal of this paper is to show how the symbolic computation capabilities of Mathematica allow us to explore the spectra of several classes of singular integral operators. For the one-dimensional case, nontrivial rational examples, computed with the automated process called [ASpecPaired-Scalar], are presented. For the matrix case, nontrivial essentially bounded and rational examples, computed with the analytical algorithms [AFact], [SInt], and [ASpecPaired-Matrix], are presented. In both cases, it is possible to check, for each considered paired singular integral operator, if a complex number (chosen arbitrarily) belongs to its spectrum.     

Asymptotically minimax testing ofr>2 simple hypotheses

In this paper, we consider the problem of asymptotically minimax testing ofr≥2 simple hypotheses when a general stochastic process is observed. We establish general conditions for the exponential decrease of maximal probability errors of minimax tests as the number of observations increases. At the present time, similar results for testing several multinomial schemes were obtained by Salihov [8]. Similar results for testing two simple hypotheses were obtained in [5]. In the proofs of the main results, we use the theory of large deviations ([3], [2]). In Sec. 1, the main result is proved. In Secs. 2–4, we analyze the i.i.d. case, nonhomogeneous Poisson processes, and renewal processes as examples. Published in Lietuvos Matematikos Rinkinys, Vol. 40, No. 3, pp. 313–320, July–September, 2000.     

Average-case analysis of incremental topological ordering

Many applications like pointer analysis and incremental compilation require maintaining a topological ordering of the nodes of a directed acyclic graph (DAG) under dynamic updates. All known algorithms for this problem are either only analyzed for worst-case insertion sequences or only evaluated experimentally on random DAGs. We present the first average-case analysis of incremental topological ordering algorithms. We prove an expected runtime of under insertion of the edges of a complete DAG in a random order for the algorithms of Alpern et al. (1990) [4], Katriel and Bodlaender (2006) [18], and Pearce and Kelly (2006) [23].     

一类非单调算法的收敛性质

1.搜索步长和搜索方向对于无约束最优化问题(?)f(x),其中f:R~n→R~1,f∈C~1,一般采用形如x_(k+1)=x_k+λ_kd_k(k=1,2,…)的迭代算法来求解,这里λ_k为搜索步长,d_k为搜索方向.     

Perturbation of the eigenvectors of the graph Laplacian: Application to image denoising

Patch-based denoising algorithms currently provide the optimal techniques to restore an image. These algorithms denoise patches locally in “patch-space”. In contrast, we propose in this paper a simple method that uses the eigenvectors of the Laplacian of the patch-graph to denoise the image. Experiments demonstrate that our denoising algorithm outperforms the denoising gold-standards. We provide an analysis of the algorithm based on recent results on the perturbation of kernel matrices (El Karoui, 2010) [1], [2], and theoretical analyses of patch denoising algorithms (Levin et al., 2012) [3], (Taylor and Meyer, 2012) [4].     

Allocating unfunded liability in pension valuation under uncertainty

This paper studied the cost allocation for the unfunded liability in a defined benefit pension scheme incorporating the stochastic phenomenon of its returns. In the recent literature represented by Cairns and Parker [Insurance: Mathematics and Economics 21 (1997) 43], Haberman [Insurance: Mathematics and Economics 11 (1992) 179; Insurance: Mathematics and Economics 13 (1993) 45; Insurance: Mathematics and Economics 14 (1994) 219; Insurance: Mathematics and Economics 14 (1997) 127], Owadally and Haberman [North American Actuarial Journal 3 (1999) 105], the fund level is modeled based on the plan dynamics and the returns are generated through several stochastic processes to reflect the current realistic economic perspective to see how the contribution changed as the cost allocation period increased. In this study, we generalize the previous constant value assumption in cost amortization by modeling the returns and valuation rates simultaneously. Taylor series expansion is employed to approximate the unconditional and conditional moments of the plan contribution and fund level. Hence the stability of the plan contribution and the fund size under different allocation periods could be estimated, which provide valuable information adding to the previous works.     

Schensted Algorithms for Dual Graded Graphs

This paper is a sequel to [3]. We keep the notation and terminology and extend the numbering of sections, propositions, and formulae of [3].The main result of this paper is a generalization of the Robinson-Schensted correspondence to the class of dual graded graphs introduced in [3], This class extends the class of Y-graphs, or differential posets [22], for which a generalized Schensted correspondence was constructed earlier in [2].The main construction leads to unified bijective proofs of various identities related to path counting, including those obtained in [3]. It is also applied to permutation enumeration, including rook placements on Ferrers boards and enumeration of involutions.As particular cases of the general construction, we re-derive the classical algorithm of Robinson, Schensted, and Knuth [19, 12], the Sagan-Stanley [18], Sagan-Worley [16, 29] and Haiman's [11] algorithms and the author's algorithm for the Young-Fibonacci graph [2]. Some new applications are suggested.The rim hook correspondence of Stanton and White [23] and Viennot's bijection [28] are also special cases of the general construction of this paper.In [5], the results of this paper and the previous paper [3] were presented in a form of extended abstract.     

Generating Large Sequences of Normal Maxima via Record Values

In our recent paper [4], algorithms for generating normal record values were developed. The developed algorithms were faster and more efficient than currently existing algorithms for generating normal record values. Algorithm 2.2, presented in this paper, is the most efficient algorithm among the algorithms studied in [4]. It allows generating “long” sequences of record values (up to two billion record values). In the present paper, two algorithms for generating normal maxima are proposed, one of which is based on algorithm 2.2. It also allows the generation of maxima taken from “large” samples. An algorithm for generating record times in a general continuous case is also proposed in the present paper.