Search

This paper, which is a continuation of [I. A. Alexeev, Theory Probab. Appl., 67 (2022), pp. 335-351], is concerned with a-stable distributions with complex stability index a. Sufficient conditions for membership in the domain of attraction of a-stable random variables (r.v.'s) are given, and a-stable L'evy processes and the corresponding semigroups of operators are constructed. Necessary and sufficient conditions are given for membership in the class of limit laws for sums of independent and identically distributed (i.i.d.) complex r.v.'s with complex normalization and centering. [ABSTRACT FROM AUTHOR]

Matroids and semigraphoids are discrete structures abstracting and generalizing linear independence among vectors and conditional independence among random variables, respectively. Despite the different nature of conditional independence from linear independence, deep connections between these two areas are found and are still undergoing active research. In this paper, we give a characterization of the embedding of matroids into conditional independence structures and its oriented counterpart, which leads to new axiom systems of matroids and oriented matroids. [ABSTRACT FROM AUTHOR]

Partial differential equations (PDEs) with uncertain or random inputs have been considered in many studies of uncertainty quantification. In forward uncertainty quantification, one is interested in analyzing the stochastic response of the PDE subject to input uncertainty, which usually involves solving high-dimensional integrals of the PDE output over a sequence of stochastic variables. In practical computations, one typically needs to discretize the problem in several ways: approximating an infinite-dimensional input random field with a finite-dimensional random field, spatial discretization of the PDE using, e.g., finite elements, and approximating high-dimensional integrals using cubatures such as quasi--Monte Carlo methods. In this paper, we focus on the error resulting from dimension truncation of an input random field. We show how Taylor series can be used to derive theoretical dimension truncation rates for a wide class of problems and we provide a simple checklist of conditions that a parametric mathematical model needs to satisfy in order for our dimension truncation error bound to hold. Some of the novel features of our approach include that our results are applicable to nonaffine parametric operator equations, dimensionally truncated conforming finite element discretized solutions of parametric PDEs, and even compositions of PDE solutions with smooth nonlinear quantities of interest. As a specific application of our method, we derive an improved dimension truncation error bound for elliptic PDEs with lognormally parameterized diffusion coefficients. Numerical examples support our theoretical findings. [ABSTRACT FROM AUTHOR]

A remarkable conjecture of Feige [SIAM J. Comput., 35 (2006), pp. 964-984] asserts that for any collection of n independent nonnegative, where X = Σ ni=1=i. In this paper, we investigate thisconjecture for the class of discrete log-concave probability distributions, and we prove a strengthened version. More specifically, we show that the conjectured bound 1/e holds when Xi's are independent discrete log-concave with arbitrary expectation. [ABSTRACT FROM AUTHOR]

This paper is a continuation of the program started in [W. Gangbo, S. Mayorga, and A. Święch, SIAM J. Math. Anal., 53 (2021), pp. 1320–1356]. We consider stochastic optimal control problems for systems of n particles with common noise, interacting through their empirical measures. We prove that their value functions un, when converted to functions of the empirical measures, converge uniformly on bounded sets in the Wasserstein space of probability measures to a limiting function V which is the unique so-called L-viscosity solution of the limiting Hamilton–Jacobi–Bellman (HJB) equation in the Wasserstein space. This generalizes such a result from the 2021 paper, in the sense that our drift and cost functions are allowed to be unbounded. The L-viscosity solution is defined using the lifting of the function and the HJB equation to a Hilbert space of square integrable random variables. The proof of the convergence of un to V uses PDE viscosity solution techniques. The lifted function V of V is the value function of a stochastic optimal control problem in the Hilbert space and we prove that V is C1,1 and that the problem has an optimal feedback control. Using this we then characterize V as the value function of a stochastic optimal control problem in the Wasserstein space. [ABSTRACT FROM AUTHOR]

In this paper, we analyze a method for approximating the distribution function and density of a random variable that depends in a nontrivial way on a possibly high number of independent random variables, each with support on the whole real line. Starting with the integral formulations of the distribution and density, the method involves smoothing the original integrand by preintegration with respect to one suitably chosen variable, and then applying a suitable quasi--Monte Carlo method to compute the integral of the resulting smoother function. Interpolation is then used to reconstruct the distribution or density on an interval. The preintegration technique is a special case of conditional sampling, a method that has previously been applied to a wide range of problems in statistics and computational finance. In particular, the pointwise approximation studied in this work is a specific case of the conditional density estimator previously considered by L'Ecuyer, Puchhammer, and Ben Abdellah INFORMS J. Comput., 34 (2022), pp. 1729-1748]. Our theory provides a rigorous regularity analysis of the preintegrated function, which is then used to show that the errors of the pointwise and interpolated estimators can both achieve nearly first-order convergence. Numerical results support the theory. [ABSTRACT FROM AUTHOR]

Several optimal control problems in Rd, like systems with uncertainty, control of flock dynamics, or control of multiagent systems, can be naturally formulated in the space of probability measures in Rd. This leads to the study of dynamics and viscosity solutions to the Hamilton--Jacobi--Bellman equation satisfied by the value functions of those control problems, both stated in the Wasserstein space of probability measures. Since this space can be also viewed as the set of the laws of random variables in a suitable L² space, the main aim of the paper is to study such control systems in the Wasserstein space and to investigate the relations between dynamical systems in Wasserstein space and their representations by dynamical systems in L², both from the points of view of trajectories and of (first-order) Hamilton--Jacobi--Bellman equations. [ABSTRACT FROM AUTHOR]

The present paper is the first part of a work on stable distributions with a complex stability index. We construct complex-valued random variables (r.v.'s) satisfying the usual stability condition but for a complex parameter a such that |&#945 - 1| < 1. We find the characteristic functions (ch.f.'s) of the r.v.'s thus obtained and prove that their distributions are infinitely divisible. It is also shown that the stability condition characterizes this class of stable r.v.'s. [ABSTRACT FROM AUTHOR]

Diffusion in heterogeneous media partitioned by semipermeable interfaces has a wide range of applications in the physical and life sciences, ranging from thermal conduction in composite media, gas permeation in soils, diffusion magnetic resonance imaging, drug delivery, and intercellular gap junctions. Many of these systems involve three-dimensional diffusion in an array of parallel planes with homogeneity in the lateral directions, so that they can be reduced to effective onedimensional (1D) models. In this paper we develop a probabilistic model of single-particle diffusion in 1D multilayered media by constructing a multilayered version of so-called snapping out Brownian motion (BM). The latter sews together successive rounds of reflected BM, each of which is restricted to a single layer. Each round of reflected BM is killed when the local time at one end of the layer exceeds an independent, exponentially distributed random variable. (The local time specifies the amount of time a reflected Brownian particle spends in a neighborhood of a boundary.) The particle then immediately resumes reflected BM in the same layer or the layer on the other side of the boundary with equal probability, and the process is iterated We proceed by constructing a last renewal equation for multilayered snapping out BM that relates the full probability density to the probability densities of partially reflected BM in each layer. We then show how transfer matrices can be used to solve the Laplace transformed renewal equation, and prove that the renewal equation and corresponding multilayer diffusion equation are equivalent. We illustrate the theory by analyzing the first passage time (FPT) problem for escape at the exterior boundaries of the domain. Finally, we use the renewal approach to incorporate a generalization of snapping out BM based on the encounter-based method for surface absorption; each round of reflected BM is now killed according to a nonexponential distribution for each local time threshold. This is achieved by considering a corresponding first renewal equation that relates the full probability density to the FPT densities for killing each round of reflected BM. We show that for certain configurations, nonexponential killing leads to an effective time-dependent permeability that is normalizable but heavy-tailed. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the complete f-moment convergence for randomly weighted sums of extended negatively dependent (END for short) random variables. Some results obtained in this paper extend and improve the corresponding ones of P. Li, X. Li, and K. Wu [J. Inequal. Appl., 2017 (2017), 182]. As an application of our main results, we establish the strong consistency for the least square (LS for short) estimators in the simple linear errors-in-variables (EV for short) regression models and provide a simulation study to verify our theoretical results. [ABSTRACT FROM AUTHOR]

While useful probability bounds for n pairwise independent Bernoulli random variables adding up to at least an integer k have been proposed in the literature, none of these bounds are tight in general. In this paper, we provide several results in this direction. Firstly, when k = 1, the tightest upper bound on the probability of the union of n pairwise independent events is provided in closed-form for any input marginal probability vector p ∈ [0, 1]n. To prove the result, we show the existence of a positively correlated Bernoulli random vector with transformed bivariate probabilities, which is of independent interest. Building on this, we show that the ratio of the Boole union bound and the tight pairwise independent bound is upper bounded by 4/3 and that the ratio is attained. Applications of the result in correlation gap analysis and distributionally robust bottleneck optimization are discussed. The result is extended to find the tightest lower bound on the probability of the intersection of n pairwise independent events. Secondly, for any k = 2 and input marginal probability vector p ∈ [0, 1]n, new upper bounds are derived by exploiting ordering of probabilities. Numerical examples are provided to illustrate when the bounds provide improvement over existing bounds. Lastly, we identify specific instances when the existing and the new bounds are tight, for example, with identical marginal probabilities. [ABSTRACT FROM AUTHOR]

This paper gives a survey of several directions of research connected with Chebyshev--Hermite polynomials on finite-dimensional and infinite-dimensional spaces, in particular, of approaches using the Malliavin calculus and other methods of investigation of distributions of polynomials in Gaussian random variables. We give estimates for measures of sets of large and small values, estimates of distances in total variation norm between distributions of polynomials, and results on membership of such distributions in Nikolskii--Besov classes of fractional differentiability. New results are obtained on weak convergence of measures given by polynomial densities with respect to Gaussian measures. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of sampling from a graphical model when the model itself is changing dynamically with time. This problem derives its interest from a variety of inference, learning, and sampling settings in machine learning, computer vision, statistical physics, and theoretical computer science. While the problem of sampling from a static graphical model has received considerable attention, theoretical works for its dynamic variants have been largely lacking. The main contribution of this paper is an algorithm that can sample dynamically from a broad class of graphical models over discrete random variables. Our algorithm is parallel and Las Vegas: it knows when to stop, and it outputs samples from the exact distribution. We also provide sufficient conditions under which this algorithm runs in time proportional to the size of the update on general graphical models as well as well-studied specific spin systems. In particular we obtain, for the Ising model (ferromagnetic or antiferromagnetic) and for the hardcore model the first dynamic sampling algorithms that can handle both edge and vertex updates (addition, deletion, and change of functions). The algorithms for both these models are efficient within regimes that are close to the respective uniqueness regimes, beyond which, even for the static and approximate sampling, no local algorithms were known or the problem itself is intractable. Our dynamic sampling algorithm relies on a local resampling algorithm and a new "equilibrium" property that is shown to be satisfied by our algorithm at each step and enables us to prove its correctness. This equilibrium property is robust enough to guarantee the correctness of our algorithm, helps us improve bounds on fast convergence on specific models, and should be of independent interest. [ABSTRACT FROM AUTHOR]

Recently, Wang and Hu [Theory Probab. Appl., 63 (2019), pp. 479-499] established the Berry-Esseen bounds for ρ-mixing random variables (r.v.'s) with the rate of normal approximation O(n-1/6 log n) by using the martingale method. In this paper, we establish some general results on the rates of normal approximation, which include the corresponding ones of Wang and Hu. The rate can be as high as O(n-1/5) or O(n-1/4 log1/2 n) under some suitable conditions. As applications, we obtain the Berry-Esseen bounds of sample quantiles based on ρ-mixing random samples. Finally, we also present some numerical simulations to demonstrate finite sample performances of the theoretical result. [ABSTRACT FROM AUTHOR]

Let Ord(τ) be the order of an element in the group Sn of permutations of an n-element set X. The present paper is concerned with the so-called general parametric model of a random permutation; according to this model an arbitrary fixed permutation τ from Sn is observed with the probability where ui is the number of cycles of length i of the permutation τ, {θi, i ∈ N} are some nonnegative parameters (the weights of cycles of length i of the permutation τ), and H(n) is the corresponding normalizing factor. We assume that an arbitrary permutation τn has such a distribution. The function p(n) = H(n)/n is assumed to be RO-varying at infinity with the lower index exceeding -1 (in particular, it can vary regularly), and the sequence {θi, i ε N} is bounded. Under these assumptions it is shown that the random variable lnOrd(τn). In particular, this scheme subsumes the class of random A-permutations (i.e., when θi = x{i A}), where A is an arbitrary fixed subset of the positive integers. This scheme also includes the Ewens model of random permutation, where θi ≡ θ > 0 for any i ∈ N. The limit theorem we prove here extends some previous results for these schemes. In particular, with θi ≡ 1 for any i ∈ N, the result just mentioned implies the well-known Erdos-Turan limit theorem. [ABSTRACT FROM AUTHOR]

In this paper, the Berry-Esseen bound for ρ-mixing random variables with the rate of normal approximation O(n-1/6 log n) is established under some suitable conditions. By using the Berry-Esseen bound, we further investigate the Berry-Esseen bound of sample quantiles for ρ-mixing random variables. The rate of normal approximation is shown to be O(n-1/6 log n) under some suitable conditions. In addition, the asymptotic normality of the linear weighted estimator for the nonparametric regression model based on ρ-mixing errors is studied by using the Berry-Esseen bound that we established. Some new results are obtained in the paper under much weaker dependent structures. [ABSTRACT FROM AUTHOR]

The present paper is devoted to queueing systems with regenerative input flow in the presence of heavy tails. Our goal is to develop an asymptotics for the probability of the waiting time process in a stationary regime to exceed a high level. In this paper, we consider the total service time of customers arriving during the time-interval [0, t] as an input flow X(t). This allows us to consider a case when the service times {ηn}∞n=1 are dependent random variables that, besides, may be dependent on a number of customers arriving in [0, t]. We obtain conditions for the virtual waiting time process in steady state to have a subexponential distribution function. We apply this result to a system with a Markov modulated semi-Markov input flow. We also consider a queue with a doubly stochastic Poisson flow in the case when the random intensity is a regenerative process. We show that these results could be transferred to corresponding systems with an unreliable server. [ABSTRACT FROM AUTHOR]

Let ξ1, ξ2, . . . be a sequence of independent copies of a random variable (r.v.) ξ, ... is the Legendre transform of A(λ). In this paper, which is partially a review to some extent, we consider generalization of the exponential Chebyshev-type inequalities P(Sn ≥ αn) ≤ exp{-nΛ(α)}, α ≥ Eξ, for the following three cases: I. Sums of random vectors, II. stochastic processes (the trajectories of random walks), and III. random fields associated with Erdős--Réenyi graphs with weights. It is shown that these generalized Chebyshev-type inequalities enable one to get exponentially unimprovable upper bounds for the probabilities to hit convex sets and also to prove the large deviation principles for objects mentioned in I--III. [ABSTRACT FROM AUTHOR]

The interrelation between signs and permutations in maximum inequalities is studied in this paper. The relationship is based on a lemma that reduces a rearrangement problem to a problem of choosing signs. It helps simplify proofs and find new facts and general settings. The following inequality is one of the main results of the paper: Let x1, ..., xn Σnk=1 xk = 0, be a collection of elements of a normed space X. Then for any collection of signs θ=(θ1,...,θn) and any t > 0, P {π: max1≧k≧n ‖ Σk1 xπ(i) ‖>t} ≧CP {π: max 1≧k≧n ‖Σk1 xπ(i)Σ‖> t/c} where π ϵ IIn, Πn is the group of all permutations of {1, ..., n}, P is the uniform distribution on it, and C is an absolute constant. The inequality is unimprovable (the inverse inequality also holds with some other constant); it generalizes well-known results due to Garsia; Maurey, and Pisier; Kashin and Saakyan; Chobanyan and Salehi; and Levental. All the inequalities of this paper can be restated as maximum inequalities for exchangeable random variables. [ABSTRACT FROM AUTHOR]

Data points from many recent real applications usually have a multiview structure in the sense that they are drawn from a multivariate random variable v\in Rn that can be partitioned into multiple, say, m, subvariables (i.e., multiview) vi ∈ Rni for i = 1, . . .,m and ∑ m i=1 ni = n. The multiview canonical correlation analysis is a statistical approach which fuses each subvariable vi into a reduced one si = xTi vi so that the fused m random variables achieve the maximum of a certain type of correlation. Among many criteria that measure the correlation, one of the earliest rules is to maximize the sum of all pairwise correlations subject to the ellipsoidal constraint of each xi. The model is commonly referred to as the maximal correlation problem (MCP), and the associated KKT system is called the multivariate eigenvalue problem (MEP). Existing methods for MCP and/or MEP may encounter slow convergence or be inapplicable in applications with high-dimensional features. This paper proposes a Krylov subspace-type method by exploiting the special structure of the ellipsoidal constraint of xi. Both the global convergence and the local convergence rate are studied, and numerical verification of the efficiency is carried out on both synthetic examples and applications of the unsupervised feature fusion with real data. [ABSTRACT FROM AUTHOR]i. The model is commonly referred to as the maximal correlation problem (MCP), and the associated KKT system is called the multivariate eigenvalue problem (MEP). Existing methods for MCP and/or MEP may encounter slow convergence or be inapplicable in applications with high-dimensional features. This paper proposes a Krylov subspace-type method by exploiting the special structure of the ellipsoidal constraint of xi. Both the global convergence and the local convergence rate are studied, and numerical verification of the efficiency is carried out on both synthetic examples and applications of the unsupervised feature fusion with real data. [ABSTRACT FROM AUTHOR]

Let X,X1, . . .,Xn be independent identically distributed random variables. In this paper we study the behavior of the concentration functions of the weighted sums ∑nk=1 Xkak depending on the arithmetic structure of the coefficients ak. The results obtained the last 10 years for the concentration functions of weighted sums play an important role in the study of singular numbers of random matrices. Recently, Tao and Vu proposed a so-called inverse principle for the Littlewood-Offord problem. We discuss the relations between this inverse principle and a similar principle for sums of arbitrarily distributed independent random variables formulated by Arak in the 1980s. [ABSTRACT FROM AUTHOR]

In this paper we modify the Stein method and the auxiliary technique of distributional transformations of random variables. This enables us to estimate the convergence rate of distributions of normalized geometric sums to the Laplace law. For independent summands, the developed approach provides an optimal estimate involving the ideal metric of order 3. New results are also obtained for the Kolmogorov and Kantorovich metrics. [ABSTRACT FROM AUTHOR]

This paper considers the concentration of values of functions of random variables sampled without replacement from a fixed finite set close to their expectations—a problem which is relevant to a variety of applications, including the transductive formulation of statistical learning theory. Apart from the review of known results, the paper studies two general approaches leading in many cases to sufficiently exact concentration inequalities. The first is based on the sub-Gaussian inequality of Bobkov [Ann. Probab., 32 (2004), pp. 2884-2907] for functions defined on a slice of the discrete cube. The second approach proposed by Hoeffding [J. Amer. Statist. Assoc., 58 (1963), pp. 13-30] reduces the problem to studying a sample of independent random variables. [ABSTRACT FROM AUTHOR]

We consider the small deviation probability for a random walk with random environment in time. Compared to [A. A. Mogul'skii, Theory Probab. Appl., 19 (1975), pp. 726-736], for the independent and identically distributed (i.i.d.) random walk, the rate is smaller (due to the random environment), which is specified in terms of the quenched and annealed variance. [ABSTRACT FROM AUTHOR]

Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors v1, . . ., vm È Rd and a constraint family B \subseteq 2[m], find a set S ÈB that maximizes the squared volume of the simplex spanned by the vectors in S. A motivating example is the ubiquitous data-summarization problem in machine learning and information retrieval where one is given a collection of feature vectors that represent data such as documents or images. The volume of a collection of vectors is used as a measure of their diversity, and partition or matroid constraints over [m] are imposed in order to ensure resource or fairness constraints. Even with a simple cardinality constraint (B = ([m] r), the problem becomes NP-hard and has received much attention starting with a result by Khachiyan [J. Complexity, 11 (1995) pp. 138--153] who gave an rO(r) approximation algorithm for a special case of this problem. Recently, Nikolov and Singh [Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, 2016, pp. 192-- 201] presented a convex program and showed how it can be used to estimate the value of the most diverse set when there are multiple cardinality constraints (i.e., when \scrB corresponds to a partition matroid). Their proof of the integrality gap of the convex program relied on an inequality by Gurvits [Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, ACM, 2006, pp. 417--426], and was recently extended to regular matroids [Straszak and Vishnoi, Proceedings of the Forty-ninth ACM SIGACT Symposium on Theory of Computing, 2017, pp. 370--383] and [Anaris and Gharan, Proceedings of the Forty-ninth Annual SIGACT Symposium on Theory of Computing, 2017, pp. 384--396] and general matroids [Anari, Gharan, and Vinzant, Proceedings of the Fifty-ninth IEEE Annual Symposium on Foundations of Computer Science, 2018, pp. 35-- 46]. The question of whether these estimation algorithms can be converted into the more useful approximation algorithms--that also output a set--remained open. The main contribution of this paper is to give the first approximation algorithms for both partition and regular matroids. We present novel formulations for the subdeterminant maximization problem, for these matroids; this reduces them to the problem of finding a point that maximizes the absolute value of a nonconvex function over a Cartesian product of probability simplices. The technical core of our results is a new anti-concentration inequality for dependent random variables that arise from these functions, which allows us to relate the optimal value of these nonconvex functions to their value at a random point. Unlike prior work on the constrained subdeterminant maximization problem, our proofs do not rely on real-stability or convexity and could be of independent interest both in algorithms and complexity where anti-concentration phenomena have recently been deployed. [ABSTRACT FROM AUTHOR]

Probabilistic models are proposed for bounding the forward error in the numerically computed inner product (dot product, scalar product) between two real n-vectors. We derive probabilistic perturbation bounds as well as probabilistic roundoff error bounds for the sequential accumulation of the inner product. These bounds are nonasymptotic, explicit, with minimal assumptions, and with a clear relationship between failure probability and relative error. The roundoffs are represented as bounded, zero-mean random variables that are independent or have conditionally independent means. Our probabilistic bounds are based on Azuma's inequality and its associated martingale, which mirrors the sequential order of computations. The derivation of forward error bounds "from first principles" has the advantage of producing condition numbers that are customized for the probabilistic bounds. Numerical experiments confirm that our bounds are more informative, often by several orders of magnitude, than traditional deterministic bounds--even for small vector dimensions n and very stringent success probabilities. In particular the probabilistic roundoff error bounds are functions of n rather than n, thus giving a quantitative confirmation of Wilkinson's intuition. The paper concludes with a critical assessment of the probabilistic approach. [ABSTRACT FROM AUTHOR]

In this paper, we will present a strong (or pathwise) approximation of standard Brownian motion by a class of orthogonal polynomials. The coefficients that are obtained from the expansion of Brownian motion in this polynomial basis are independent Gaussian random variables. Therefore, it is practical (i.e., requires N independent Gaussian coefficients) to generate an approximate sample path of Brownian motion that respects integration of polynomials with degree less than N. Moreover, since these orthogonal polynomials appear naturally as eigenfunctions of the Brownian bridge covariance function, the proposed approximation is optimal in a certain weighted L²(P) sense. In addition, discretizing Brownian paths as piecewise parabolas gives a locally higher order numerical method for stochastic differential equations (SDEs) when compared to the piecewise linear approach. We shall demonstrate these ideas by simulating inhomogeneous geometric Brownian motion (IGBM). This numerical example will also illustrate the deficiencies of the piecewise parabola approximation when compared to a new version of the asymptotically efficient log-ODE (or Castell--Gaines) method. [ABSTRACT FROM AUTHOR]

In this paper we present a discontinuous Galerkin (DG) method to approximate stochastic conservation laws, which is an efficient high-order scheme. We study the stability for the semidiscrete DG methods for fully nonlinear stochastic equations. Error estimates are obtained for smooth solutions of semilinear stochastic equations with variable coefficients. We also estab- lish a derivative-free second-order time discretization scheme for matrix-valued stochastic ordinary differential equations. Numerical experiments are performed to confirm the analytical results. [ABSTRACT FROM AUTHOR]

We consider statistics of the form T = Pn j=1 jfj +R, where j, fj, j = 1, . . ., n, and R are M-measurable random variables for some s-algebra M. Assume that there exist s-algebras M(1), . . . ,M(n), M(j) M, j = 1, . . ., n, such that E(j | M(j)) = 0. Under these assumptions, we prove an inequality for E|T|p with p > 2. We also discuss applications of the main result of the paper to estimation of moments of linear forms, U-statistics, and perturbations of the characteristic equation for the Stieltjes transform of Wigner's semicircle law. [ABSTRACT FROM AUTHOR]

A random vector X is weakly stable if and only if for all a, b ∈ ℝ there exists a random variable Θ such that aX + bX' ... XΘ, where X' is an independent copy of X and Θ is independent of X. This is equivalent (see [J. K. Misiewicz, K. Oleszkiewicz, and K. Urbanik, Studia Math., 167 (2005), pp. 195-213]) to the condition that for all random variables Q1,Q2 there exists a random variable Θ such that XQ1 +X'Q2 ... XΘ, where X,X',Q1,Q2,Θ are independent. In this paper we define a weak generalized convolution of measures defined by the formula L(Q1) ⊗μ L(Q2) = L(Θ), if the former equation holds for X,Q1,Q2,Θ and μ = L(X). We study here basic properties of this convolution and basic properties of distributions which are infinitely divisible in the sense of this convolution. The main result of this paper is the analogue of the Lévy-Khintchine representation theorem for ⊗μ-infinitely divisible distributions. [ABSTRACT FROM AUTHOR]

The present paper studies the connection between the local limit theorem for lattice random variables and the corresponding symmetrized random variables. An example is constructed to show that the local limit theorem holds for some sequence of symmetrized random variables, but fails to hold for the original random variables. [ABSTRACT FROM AUTHOR]

In this paper, a regularization of Wasserstein barycenters for random measures supported on Rd is introduced via convex penalization. The existence and uniqueness of such barycenters is first proved for a large class of penalization functions. The Bregman divergence associated to the penalization term is then considered to obtain a stability result on penalized barycenters. This allows the comparison of data made of n absolutely continuous probability measures, within the more realistic setting where one only has access to a dataset of random variables sampled from unknown distributions. The convergence of the penalized empirical barycenter of a set of n independent and identically distributed random probability measures toward its population counterpart is finally analyzed. This approach is shown to be appropriate for the statistical analysis of either discrete or absolutely continuous random measures. It also allows one to construct, from a set of discrete measures, consistent estimators of population Wasserstein barycenters that are absolutely continuous. [ABSTRACT FROM AUTHOR]

A solution of two-stage stochastic generalized equations is a pair: a first stage solution which is independent of realization of the random data and a second stage solution which is a function of random variables. This paper studies convergence of the sample average approximation of two-stage stochastic nonlinear generalized equations. In particular, an exponential rate of the convergence is shown by using the perturbed partial linearization of functions. Moreover, sufficient conditions for the existence, uniqueness, continuity, and regularity of solutions of two-stage stochastic generalized equations are presented under an assumption of monotonicity of the involved functions. These theoretical results are given without assuming relatively complete recourse and are illustrated by two-stage stochastic noncooperative games of two players. [ABSTRACT FROM AUTHOR]

This paper gives an overview of multivariate local limit theorems for integer random vectors and provides the sufficient condition for local limit theorems in Rn. [ABSTRACT FROM AUTHOR]

Considering first-order stochastic dominance constraints for random variables arising as optimal values of stochastic programs with linear recourse, verifiable sufficient conditions for metric regularity are presented. A growth condition developed in [R. Henrion and W. Romisch, Math. Program., 84 (1999), pp. 55-88] has a crucial role in the analysis of the present paper. Implications regarding stability and sensitivity of optimal values and optimal solutions of stochastic optimization problems involving the dominance constraints considered conclude the paper. [ABSTRACT FROM AUTHOR]

We propose a computationally efficient fully polynomial-time approximation scheme (FPTAS) to compute an approximation with arbitrary precision of the value function of convex stochastic dynamic programs, using the technique of $K$-approximation sets and functions introduced by Halman et al. [Math. Oper. Res., 34, (2009), pp. 674--685]. This paper deals with the convex case only, and it has the following contributions. First, we improve on the worst-case running time given by Halman et al. Second, we design and implement an FPTAS with excellent computational performance and show that it is faster than an exact algorithm even for small problem instances and small approximation factors, becoming orders of magnitude faster as the problem size increases. Third, we show that with careful algorithm design, the errors introduced by floating point computations can be bounded, so that we can provide a guarantee on the approximation factor over an exact infinite-precision solution. We provide an extensive computational evaluation based on randomly generated problem instances coming from applications in supply chain management and finance. The running time of the FPTAS is both theoretically and experimentally linear in the size of the uncertainty set. [ABSTRACT FROM AUTHOR]

Let X be a countable discrete Abelian group containing no elements of order 2, α be an automorphism of X, and ξ1 and ξ2 be independent random variables with values in the group X and having distributions μ1 and μ2. The main result of the present paper is as follows. The symmetry of the conditional distribution of the linear form L2 = ξ1 +αξ2 given L1 = ξ1 +ξ2 implies that μj are shifts of the Haar distribution of a finite subgroup of X if and only if the automorphism α satisfies the condition Ker(I +α) = {0}. This theorem is an analogue, for discrete Abelian groups, of the well-known Heyde theorem, where a Gaussian distribution on the real line is characterized by the symmetry of the conditional distribution of one linear form of independent random variable given the other. We also prove some generalizations of this theorem. [ABSTRACT FROM AUTHOR]

In this paper we study the asymptotic distributions, under appropriate normalization, of the sum ... and the lt norm Rt = St1/t, when Nt → ∞ as t → ∞ and X1,X2, . . . are independent and identically distributed random variables in the maximum domain of attraction of the reverse-Weibull distribution. [ABSTRACT FROM AUTHOR]

Let φn,K denote the largest angle in all the triangles with vertices among the n points selected at random in a compact convex subset K of Rd with nonempty interior, where d ≥ 2. It is shown that the distribution of the random variable λd(K) n3/3! (π - φn,K)d-1, where λd(K) is a certain positive real number which depends only on the dimension d and the shape of K, converges to the standard exponential distribution as n→∞. By using the Steiner symmetrization, it is also shown that λd(K), which is referred to in the paper as the elongation of K, attains its minimum if and only if K is a ball B(d) in Rd. Finally, the asymptotics of λd(B(d)) for large d is determined. [ABSTRACT FROM AUTHOR]

In this paper we study the asymptotic behavior of the tail probability P(V 2 < r) as r → 0, where the sum V 2 is given by the formula V 2 = a2Σi,j≥1(i+β)-2c(j+δ)-2ξ2 ij. Here {ξij} are independent standard Gaussian random variables, and a > 0, β > -1, δ > -1, c > 1/2, ≠= 1 are some constants. Thus, we study small deviations of the L2-norm of certain two-parameter Gaussian random fields, that have the structure of a tensor product. [ABSTRACT FROM AUTHOR]

A graphic sequence \pi is potentially H-graphic if there is some realization of \pi that contains H as a subgraph. The Erd\"os--Jacobson--Lehel problem asks one to determine \sigma (H, n), the minimum even integer such that any n-term graphic sequence \pi with sum at least \sigma (H, n) is potentially H-graphic. The parameter \sigma (H, n) is known as the potential function of H, and can be viewed as a degree sequence variant of the classical extremal function ex(n,H). Recently, Ferrara et al. [Combinatorica 36 (2016), pp. 687--702] determined \sigma (H, n) asymptotically for all H, which is analogous to the Erd\"os--Stone--Simonovits theorem that determines ex(n,H) asymptotically for nonbipartite H. In this paper, we investigate a stability concept for the potential number, inspired by Simonovits' classical result on the stability of the extremal function. We first define a notion of stability for the potential number that is a natural analogue to the stability given by Simonovits. However, under this definition, many families of graphs are not \sigma -stable, establishing a stark contrast between the extremal and potential functions. We then give a sufficient condition for a graph H to be stable with respect to the potential function, and characterize the stability of those graphs H that contain an induced subgraph of order \alpha (H) + 1 with exactly one edge. [ABSTRACT FROM AUTHOR]

Mubayi's conjecture states that if\scrF is a family of k-sized subsets of [n] = {1, . . ., n} which, for k ≥ d ≥ 3 and n ≥ dk/d-1, satisfies A1 ∩ ... ∩ Ad ≠ Ø whenever |A1 ∪ .... ∪ Ad| ≤ 2k for all distinct sets A1, ..., Ad ∊ F, then |F| ≤ (k-1), with equality occurring only if F is the family of all k-sized subsets containing some fixed element. This paper proves that Mubayi's conjecture is true for all families that are invariant with respect to shifting; indeed, these families satisfy a stronger version of Mubayi's conjecture. Relevant to the conjecture, we prove a fundamental bijective duality between what we call (i, j)-unstable families and (j, i)-unstable families. Generalizing previous intersecting conditions, we introduce the (d, s, t)-conditionally intersecting condition for families of sets and prove general results thereon. We prove fundamental theorems on two (d, s)-conditionally intersecting families that generalize previous intersecting families, and we pose an extension of a previous conjecture by Frankl and Füredi. Finally, we generalize a classical result by ErdÕs, Ko, and Rado by proving tight upper bounds on the size of (2, s)-conditionally intersecting families F ⊆ 2n-1), with equality occurring only if F is the family of all k-sized subsets containing some fixed element. This paper proves that Mubayi's conjecture is true for all families that are invariant with respect to shifting; indeed, these families satisfy a stronger version of Mubayi's conjecture. Relevant to the conjecture, we prove a fundamental bijective duality between what we call (i, j)-unstable families and (j, i)-unstable families. Generalizing previous intersecting conditions, we introduce the (d, s, t)-conditionally intersecting condition for families of sets and prove general results thereon. We prove fundamental theorems on two (d, s)-conditionally intersecting families that generalize previous intersecting families, and we pose an extension of a previous conjecture by Frankl and Füredi. Finally, we generalize a classical result by ErdÕs, Ko, and Rado by proving tight upper bounds on the size of (2, s)-conditionally intersecting families F ⊆ 2[n] and by characterizing the families that attain these bounds. We extend this theorem for sufficiently large n to families F ⊆ 2[n] whose members have at most a fixed size u. [ABSTRACT FROM AUTHOR]

An anagram is a word of the form WP where W is a non-empty word and P is a permutation of W. A vertex coloring of a graph is anagram-free if no subpath of the graph is an anagram. Anagram-free graph coloring was independently introduced by Kam\v cev, Łuczak, and Sudakov [Combin. Probab. Comput., 27 (2018), pp. 623--642] and ourselves [Electron. J. Combin., 25 (2018), pp. 2--20]. In this paper we introduce the study of anagram-free colorings of graph subdivisions. We show that every graph has an anagram-free 8-colorable subdivision. The number of division vertices per edge is exponential in the number of edges. For trees, we construct anagram-free 10-colorable subdivisions with fewer division vertices per edge. Conversely, we prove lower bounds, in terms of division vertices per edge, on the anagram-free chromatic number for subdivisions of the complete graph and subdivisions of complete trees of bounded degree. [ABSTRACT FROM AUTHOR]

The Chordal Vertex Deletion (CHVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for CHVD under the parameterization by the solution size. Using a new Erdõs-Pósa-type packing/covering duality for holes in nearly chordal graphs, we present a polynomial-time algorithm that reduces any instance (G, k) of CHVD to an equivalent instance with poly(k) vertices. The existence of a polynomial kernel answers an open problem posed by Marx in 2006 [D. Marx, "Chordal Deletion Is Fixed-Parameter Tractable," in Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci. 4271, Springer, 2006, pp. 37-48]. To obtain the kernelization, we develop the first poly(opt)-approximation algorithm for CHVD, which is of independent interest. In polynomial time, it either decides that G has no chordal deletion set of size k, or outputs a solution of size O(k4log² k). [ABSTRACT FROM AUTHOR]

In this paper, we study the connectivity properties of the random subgraph of the n-cube generated by the k-out model and denoted by Qn(k). Let k be an integer, 1 ≤ k ≤ n-1. We let Qn(k) be the graph that is generated by independently including for every ν ∊ V(Qn) a set of k distinct edges chosen uniformly from all the (k n) sets of distinct edges that are incident to ν. We study the connectivity properties of Qn(k) as k varies. We show that without high probability (w.h.p.), Qn(1) does not contain a giant component i.e., a component that spans Ω(2n) vertices. Thereafter, we show that such a component emerges when k=2. In addition, the giant component spans all but o(2n) vertices, and hence it is unique. We then establish the connectivity threshold found at k0=log2 n-2log2log2 n. The threshold is sharp in the sense that Qn([k0]) is disconnected but Qn([k0]+1) is connected w.h.p. Furthermore, we show that w.h.p., Qn(k) is k-connected for every k≥ [k0]+1. [ABSTRACT FROM AUTHOR]

For given simple graphs G1 and G2, the size Ramsey number Ȓ(G1,G2) is the smallest positive integer m, where there exists a graph G with m edges such that in any edge coloring of G with two colors red and blue, there is either a red copy of G1 or a blue copy of G2. In 1981, Erdös and Faudree investigated the size Ramsey number Ȓ(Kn, tK2), where Kn is a complete graph on n vertices and tK2 is a matching of size t. They obtained the value of Ȓ(Kn, tK2) when n ≥ 4t-1 as well as for t = 2 and asked for the behavior of these numbers when t is much larger than n. In this regard, they posed the following interesting question: For every positive integer n, is it true that ... In this paper, we obtain the exact value of Ȓ(Kn, tK2) for every pair of positive integers n, t, and as a byproduct, we give an affirmative answer to the question of Erdös and Faudree. [ABSTRACT FROM AUTHOR]

The concept of m-negatively orthant dependent (m-NOD) random variables is introduced, and the moment inequalities for m-NOD random variables, especially the Marcinkiewicz- Zygmund-type inequality and Rosenthal-type inequality, are established. As one application of the moment inequalities, we study the Lr convergence and strong convergence for m-NOD random variables under some uniformly integrable conditions. On the other hand, the asymptotic approximation of inverse moments for nonnegative m-NOD random variables with finite first moments is established. The results obtained in the paper generalize or improve some known ones for independent sequences and some dependent sequences. [ABSTRACT FROM AUTHOR]

This paper studies a probabilistic characteristic called buffered probability of exceedance (bPOE). It is a function of a random variable and a real-valued threshold. By definition, bPOE is the probability of a tail such that the average of this tail equals the threshold. This characteristic is an extension of the so-called buffered failure probability and it is equal to one minus inverse of the conditional value-at-risk (CVaR). bPOE is a quasi-convex function of the random variable w.r.t. the regular addition operation and a concave function w.r.t. the mixture operation; it is a monotonic function of the random variable; it is a strictly decreasing function of the threshold on the interval between the expectation and the essential supremum. The multiplicative inverse of the bPOE is a convex function of the threshold, and a piecewise-linear function in the case of discretely distributed random variable. The paper provides efficient calculation formulas for bPOE. Minimization of bPOE is reduced to a convex program for a convex feasible region and to linear programming for a polyhedral feasible region and discretely distributed random variables. A family of bPOE minimization problems and corresponding CVaR minimization problems share the same set of optimal solutions. [ABSTRACT FROM AUTHOR]

In this paper, we consider stochastic optimization problems with kth order dominance constraints induced by full random recourse. We first introduce the optimization model with dominance constraints and its distributionally robust counterpart. After establishing the closedness and convexity of the feasible solution set, we derive the qualitative stability about the constraint set mapping with respect to the simultaneous perturbations of the random variable and the benchmark. Furthermore, we obtain the quantitative stability results of the constraint set mapping, the optimal value function and the optimal solution set under the Hausdorff metric, which extend the present results to the locally Lipschitz continuity case. Finally, for stochastic optimization problems with kth order distributionally robust dominance constraints, we derive the corresponding quantitative stability results under the appropriate pseudometric. [ABSTRACT FROM AUTHOR]