Search

In this paper, we provide a construction of two algorithms for approximation of the system of the jump-diffusion SDEs. Both methods are based on the classical Milstein steps and use equidistant discretization points. We construct implementable algorithm and their derivative-free version. We show that constructed methods are asymptotically optimal in the class of methods that use equidistant discretization of the interval [ 0 , T ]. Moreover, we report numerical experiments performed for some test equations, which confirm theoretical properties. [ABSTRACT FROM AUTHOR]

In this paper, we deal with the global approximation of solutions of stochastic differential equations (SDEs) driven by countably dimensional Wiener process. Under certain regularity conditions imposed on the coefficients, we show lower bounds for exact asymptotic error behaviour. For that reason, we analyse separately two classes of admissible algorithms: based on equidistant, and possibly not equidistant meshes. Our results indicate that in both cases, decrease of any method error requires significant increase of the cost term, which is illustrated by the product of cost and error diverging to infinity. This is, however, not visible in the finite-dimensional case. In addition, we propose an implementable, path-independent Euler algorithm with adaptive step-size control, which is asymptotically optimal among algorithms using specified truncation levels of the underlying Wiener process. Our theoretical findings are supported by numerical simulation in Python language. [ABSTRACT FROM AUTHOR]

To search for the Slichter mode (1S1), the longest mode of Earth's free oscillations, long-term (more than 15 years) strain data of the Baksan laser interferometer–strainmeter (with a measuring-arm length of 75 m) of Sternberg Astronomical Institute, Moscow State University (SAI MSU) (Elbrus region, North Caucasus) are used. The detection and estimation of the Slichter mode is performed according to our developed asymptotically optimal algorithm for data analysis with allowance for the properties of seismic noise and mode features, including the parameters of its splitting. The hypothesis of the constant mode excitation is tested. The most probable periods of the Slichter mode and the values ​​of the splitting parameter are determined, and the statistical reliability of the detection is estimated. [ABSTRACT FROM AUTHOR]

Abstract—The Slichter mode (1S1) is the longest-period mode of the free oscillations of the Earth. The period of the Slichter mode directly depends on density jump between the outer liquid and the inner solid core which makes the detection of this oscillation very important for gaining a more detailed insight into the structure of the Earth's interior. Reliable empirical data on the detection of Slichter mode are absent, which is associated with the rather low amplitude of this mode on the surface. In this work, for the first time, an attempt is made to detect the Slichter mode using the strain data from the largest 2010 Chilean earthquake recorded by the Baksan laser interferometer–strainmeter (Sternberg Astronomical Institute of the Moscow State University (SAI MSU)) with a measuring arm length of 75 m in the Elbrus region, North Caucasus. An asymptotically optimal data analysis algorithm that allows for the properties of seismic noise and peculiarities of the mode is developed. Simultaneously with mode detection, the algorithm provides evaluation of mode parameters (frequency and splitting magnitude). Statistical reliability of the detection is estimated; the parameters of the Slichter mode and the corresponding density jump between the inner and outer core of the Earth are determined. [ABSTRACT FROM AUTHOR]

The paper deals with strong global approximation of stochastic differential equations (SDEs) driven by two independent processes: a nonhomogeneous Poisson process and a Wiener process. We assume that the jump and diffusion coefficients of the underlying SDE satisfy jump commutativity condition (see Chapter 6.3 in [21]). We establish the exact convergence rate of minimal errors that can be achieved by arbitrary algorithms based on a finite number of observations of the Poisson and Wiener processes. We consider classes of methods that use equidistant or nonequidistant sampling of the Poisson and Wiener processes. We provide a construction of optimal methods, based on the classical Milstein scheme, which asymptotically attain the established minimal errors. The analysis implies that methods based on nonequidistant mesh are more efficient, with respect to asymptotic constants, than those based on the equidistant mesh. [ABSTRACT FROM AUTHOR]

We consider one of the central intractable problems of logical data analysis - finding maximal independent elements of partial orders (dualization of a product of partial orders). An important particular case is considered with each order a chain. If each chain is of cardinality 2, the problem involves the construction of a reduced disjunctive normal form of a monotone Boolean function defined by a conjunctive normal form. An asymptotic expression is obtained for a typical number of maximal independent elements of products for a large number of finite chains. The derivation of such asymptotic bounds is a technically complex problem, but it is necessary for the proof of existence of asymptotically optimal algorithms for the monotone dualization problem and the generalization of this problem to chains of higher cardinality. An asymptotically optimal algorithm is described for the problem of dualization of a product of finite chains. [ABSTRACT FROM AUTHOR]

Abstract: Issues related to the construction of efficient algorithms for intractable discrete problems are studied. Enumeration problems are considered. Their intractability has two aspects—exponential growth of the number of their solutions with increasing problem size and the complexity of finding (enumerating) these solutions. The basic enumeration problem is the dualization of a monotone conjunctive normal form or the equivalent problem of finding irreducible coverings of Boolean matrices. For the latter problem and its generalization for the case of integer matrices, asymptotics for the typical number of solutions are obtained. These estimates are required, in particular, to prove the existence of asymptotically optimal algorithms for monotone dualization and its generalizations. [ABSTRACT FROM AUTHOR]

We provide a construction of an implementable method based on path-independent adaptive step-size control for global approximation of jump-diffusion SDEs. The sampling points are chosen in nonadaptive way with respect to trajectories of the driving Poisson and Wiener processes. However, they are adapted to the diffusion and jump coefficients of the underlying stochastic differential equation and to the values of intensity function of the driving Poisson process. The method is asymptotically optimal in the class of methods that use (possibly) non-equidistant discretization of the interval [ 0 , T ] and is more efficient than any method based on the uniform mesh. [ABSTRACT FROM AUTHOR]

We consider strong global approximation of SDEs driven by a homogeneous Poisson process with intensity λ > 0. We establish the exact convergence rate of minimal errors that can be achieved by arbitrary algorithms based on a finite number of observations of the Poisson process. We consider two classes of methods using equidistant or nonequidistant sampling of the Poisson process, respectively. We provide a construction of optimal schemes, based on the classical Euler scheme, which asymptotically attain the established minimal errors. It turns out that methods based on nonequidistant mesh are more efficient than those based on the equidistant mesh. [ABSTRACT FROM AUTHOR]

Distribution matching transforms independent and Bernoulli(1/2) distributed input bits into a sequence of output symbols with a desired distribution. Fixed-to-fixed length, invertible, and low complexity encoders and decoders based on constant composition and arithmetic coding are presented. The encoder achieves the maximum rate, namely, the entropy of the desired distribution, asymptotically in the blocklength. Furthermore, the normalized divergence of the encoder output and the desired distribution goes to zero in the blocklength. [ABSTRACT FROM AUTHOR]

The design of efficient on average algorithms for discrete enumeration problems is studied. The dualization problem, which is a central enumeration problem, is considered. New asymptotically optimal dualization algorithms are constructed. It is shown that they are superior in time costs to earlier constructed asymptotically optimal dualization algorithms and other available dualization algorithms with different design features. [ABSTRACT FROM AUTHOR]

Asymptotic estimates for the typical number of irreducible coverings and the typical length of an irreducible covering of a Boolean matrix are obtained in the case when the number of rows is no less than the number of columns. As a consequence, asymptotic estimates are obtained for the typical number of maximal conjunctions and the typical rank of a maximal conjunction of a monotone Boolean function of variables defined by a conjunctive normal form of clauses. Similar estimates are given for the number of irredundant coverings and the length of an irredundant covering of an integer matrix (for the number of maximal conjunctions and the rank of a maximal conjunction of a two-valued logical function defined by its zero set). Results obtained previously in this area are overviewed. [ABSTRACT FROM AUTHOR]