Stochastic Bounds for the Sparre Andersen Process

In this paper we define two stochastic processes that are smaller and greater in usual stochastic order than the Sparre Andersen process. We derive, as a consequence, upper and lower bounds of its marginal distributions, and of the distributions of its first passage times above fixed thresholds. We also present a generalization of these stochastic bounds for risk processes perturbed by diffusion.AMS 2000 Subject Classification: 60K10, 60E15Partially supported by the italian PRIN-Cofin 2004 “Stochastic models in mathematical finance” (F. Pellerey) and PRIN-Cofin 2003 “Numerical, analytical and simulation methods with reference to reliability in neuronal signal transmission” (C. Zucca).     

Diffusion in layered media at large times

The large-time asymptotic behavior of the Green's function for the one-dimensional diffusion equation is found in two cases: 1) the potential is a function with compact support; 2) the potential is a periodic function of the coordinates. In the first case, the asymptotic behavior of the Green's function can be expressed in terms of the elements of theS matrix of the corresponding Schrödinger operator for negative values of the energy on the spectral plane. In the second case, the asymptotic behavior can be expressed in terms of Floquet-Bloch functions of the corresponding Hille operator at negative values of the energy on the spectral plane. The results are used to study diffusion in layered media at large times. The case of external force is also considered. In the periodic case, the Seeley coefficients are found.Institute of Problems of Mechanical Engineering, Russian Academy of Sciences. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 98, No. 1, pp. 106–148, January, 1994.     

A random walk proof of the Erdős-Taylor conjecture

Summary For the simple random walk in ]]>\mathbb{Z}^2$ we study those points which are visited an unusually large number of times, and provide a new proof of the Erdős-Taylor Conjecture describing the number of visits to the most visited point.     

暂留对称扩散过程全占据时的大偏差

本文讨论暂留对称扩散过程的全占据时的大偏差．我们证明在一致椭圆条件下,暂留对称扩散过程的全占据时满足大偏差原理．     

分形多孔介质中的奇异扩散

分形多孔介质和均质多孔介质相比具有许多特殊的性质,它在各个不同的尺度上有相互钳套的自相似结构.孔隙分形中的粒子扩散和经典的Fick扩散不同,其均方位移服从分形幂律关系.据此对孔隙分形中的粒子扩散利用随机过程的统计方法建立了奇异扩散的理论模型,讨论了奇异扩散的非马尔可夫性质和分形性质.     

Bicolored graph partitioning, or: gerrymandering at its worst

This study is motivated by an electoral application where we look into the following question: how much biased can the assignment of parliament seats be in a majority system under the effect of vicious gerrymandering when the two competing parties have the same electoral strength? To give a first theoretical answer to this question, we introduce a stylized combinatorial model, where the territory is represented by a rectangular grid graph, the vote outcome by a “balanced” red/blue node bicoloring and a district map by a connected partition of the grid whose components all have the same size. We constructively prove the existence in cycles and grid graphs of a balanced bicoloring and of two antagonist “partisan” district maps such that the discrepancy between their number of “red” (or “blue”) districts for that bicoloring is extremely large, in fact as large as allowed by color balance.     

A Diffusion Approximation for a Markovian Queue with Reneging

Consider a single-server queue with a Poisson arrival process and exponential processing times in which each customer independently reneges after an exponentially distributed amount of time. We establish that this system can be approximated by either a reflected Ornstein–Uhlenbeck process or a reflected affine diffusion when the arrival rate exceeds or is close to the processing rate and the reneging rate is close to 0. We further compare the quality of the steady-state distribution approximations suggested by each diffusion.     

Diffusion processes on graphs: stochastic differential equations,large deviation principle

Ito's rule is established for the diffusion processes on the graphs. We also consider a family of diffusions processes with small noise on a graph. Large deviation principle is proved for these diffusion processes and their local times at the vertices. Received: 12 February 1997 / Revised version: 3 March 1999     

An occupation time identity for reflecting Brownian motion with drift

Summary This note is about an occupation time identity derived in [14] for reflecting Brownian motion with drift ]]>]]>]]>]]>]]>]]>]]>]]>]]>]]>]]>]]>]]>-\mu<0,$ RBM($-\mu$), for short. The identity says that for RBM($-\mu$) in stationary state ]]>(I^{+}_t, I^{-}_t) \rr (t-G_t,D_t-t),\qquad t\in \mathbb{R},$$ where $G_t$ and $D_t$ denote the starting time and the ending time, respectively, of an excursion from 0 to 0 (straddling $t$) and $I^{+}_t$ and $I^{-}_t$ are the occupation times above and below, respectively, of the observed level at time $t$ during the excursion. Due to stationarity, the common distribution does not depend on $t.$ In fact, it is proved in [9] that the identity is true, under some assumptions, for all recurrent diffusions and stationary processes. In the null recurrent diffusion case the common distribution is not, of course, a probability distribution. The aim of this note is to increase understanding of the identity by studying the RBM($-\mu$) case via Ray--Knight theorems.     

Variational Principle for General Diffusion Problems

We employ the Monge–Kantorovich mass transfer theory to study the existence of solutions for a large class of parabolic partial differential equations. We deal with nonhomogeneous nonlinear diffusion problems (of Fokker–Planck type) with time-dependent coefficients. This work greatly extends the applicability of known techniques based on constructing weak solutions by approximation with time-interpolants of minimizers arising from Wasserstein-type implicit schemes. It also generalizes previous results of the authors, where proofs of convergence in the case of a right-hand side in the equation is given by these methods. To prove the existence of weak solutions we establish an interesting maximum principle for such equations. This involves comparison with the solution for the corresponding homogeneous, time-independent equation.     

Diffusion with irregular drift in a Hilbert space

We construct a generalized diffusion process in a separable Hilbert space. The drift of this process satisfies certain conditions of integrability with respect to the Gaussian measure. We establish the properties of the constructed process.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 47, No. 9, pp. 1224–1230, September, 1995.     

Optimal paths in bi-attribute networks with fractional cost functions

An important routing problem is to determine an optimal path through a multi-attribute network which minimizes a cost function of path attributes. In this paper, we study an optimal path problem in a bi-attribute network where the cost function for path evaluation is fractional. The problem can be equivalently formulated as the “bi-attribute rational path problem” which is known to be NP-complete. We develop an exact approach to find an optimal simple path through the network when arc attributes are non-negative. The approach uses some path preference structures and elimination techniques to discard, from further consideration, those (partial) paths that cannot be parts of an optimal path. Our extensive computational results demonstrate that the proposed method can find optimal paths for large networks in very attractive times.     

Fuzzy Relation Equations for Compression/Decompression Processes of Colour Images in the RGB and YUV Colour Spaces

We use particular fuzzy relation equations for compression/decompression of colour images in the RGB and YUV spaces, by comparing the results of the reconstructed images obtained in both cases. Our tests are made over well known images of 256×256 pixels (8 bits per pixel in each band) extracted from Corel Gallery. After the decomposition of each image in the three bands of the RGB and YUV colour spaces, the compression is performed using fuzzy relation equations of “min - →_t” type, where “t” is the Lukasiewicz t-norm and “→_t” is its residuum. Any image is subdivided in blocks and each block is compressed by optimizing a parameter inserted in the Gaussian membership functions of the fuzzy sets, used as coders in the fuzzy equations. The decompression process is realized via a fuzzy relation equation of max-t type. In both RGB and YUV spaces we evaluate and compare the root means square error (RMSE) and the consequentpeak signal to noise ratio (PSNR) on the decompressed images with respect to the original image under several compression rates.     

L-fuzzy quantifiers of type determined by fuzzy measures

The aim of this paper is, first, to introduce two new types of fuzzy integrals, namely, -fuzzy integral and →-fuzzy integral. The first integral is based on a fuzzy measure of L-fuzzy sets and the second one on a complementary fuzzy measure of L-fuzzy sets, where L is a complete residuated lattice. Some of their properties and a relation to the fuzzy (Sugeno) integral are investigated. Second, using these integrals, two classes of monadic L-fuzzy quantifiers of type 1 are defined. These L-fuzzy quantifiers can be used for modeling the semantics of natural language quantifiers like “all”, “some”, “many”, “none”, “at most half”, etc. Several semantic properties of these L-fuzzy quantifiers are studied.     

The Enumeration of Permutations with a Prescribed Number of “Forbidden” Patterns

We initiate a general approach for the fast enumeration of permutations with a prescribed number of occurrences of “forbidden” patterns that seems to indicate that the enumerating sequence is always P-recursive. We illustrate the method completely in terms of the patterns “abc,” “cab,” and “abcd.”     

Estimate for a Rearrangement of a Function Satisfying the “Reverse Jensen Inequality”

We show that an equimeasurable rearrangement of any function satisfying the “reverse Jensen inequality” with respect to various multidimensional segments also satisfies the “reverse Jensen inequality” with the same constant.__________Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 57, No. 2, pp. 158–169, February, 2005.     

Universal Graphs with Forbidden Subgraphs and Algebraic Closure

We apply model theoretic methods to the problem of existence of countable universal graphs with finitely many forbidden connected subgraphs. We show that to a large extent the question reduces to one of local finiteness of an associated “algebraic closure” operator. The main applications are new examples of universal graphs with forbidden subgraphs and simplified treatments of some previously known cases.     

Heat Diffusion on Homogeneous Trees

Let X be a homogeneous tree. We study the heat diffusion process associated with the nearest neighbour isotropic Markov operator on X. In particular it is shown that the heat maximal operator is weak type (1, 1) and strong type (p, p), for every 1 < p < ∞. We estimate the asymptotic behaviour of the heat maximal function. Moreover, we introduce a family of H^p spaces on X. It is proved that H^p=l^p(X) for 1 < p < ∞ and is conjectured that H^p for p less than 1, is trivial.     

Polynomial growth rates

We consider linear equations v^′=A(t)v with a polynomial asymptotic behavior, that can be stable, unstable and central. We show that this behavior is exhibited by a large class of differential equations, by giving necessary and sufficient conditions in terms of generalized “polynomial” Lyapunov exponents for the existence of polynomial behavior. In particular, any linear equation in block form in a finite-dimensional space, with three blocks having “polynomial” Lyapunov exponents respectively negative, positive, and zero, has a nonuniform version of polynomial trichotomy, which corresponds to the usual notion of trichotomy but now with polynomial growth rates. We also obtain sharp bounds for the constants in the notion of polynomial trichotomy. In addition, we establish the persistence under sufficiently small nonlinear perturbations of the stability of a nonuniform polynomial contraction.     

Exploiting structure in quantified formulas

We study the computational problem “find the value of the quantified formula obtained by quantifying the variables in a sum of terms.” The “sum” can be based on any commutative monoid, the “quantifiers” need only satisfy two simple conditions, and the variables can have any finite domain. This problem is a generalization of the problem “given a sum-of-products of terms, find the value of the sum” studied in [R.E. Stearns and H.B. Hunt III, SIAM J. Comput. 25 (1996) 448–476]. A data structure called a “structure tree” is defined which displays information about “subproblems” that can be solved independently during the process of evaluating the formula. Some formulas have “good” structure trees which enable certain generic algorithms to evaluate the formulas in significantly less time than by brute force evaluation. By “generic algorithm,” we mean an algorithm constructed from uninterpreted function symbols, quantifier symbols, and monoid operations. The algebraic nature of the model facilitates a formal treatment of “local reductions” based on the “local replacement” of terms. Such local reductions “preserve formula structure” in the sense that structure trees with nice properties transform into structure trees with similar properties. These local reductions can also be used to transform hierarchical specified problems with useful structure into hierarchically specified problems having similar structure.