Some Characteristic Properties of the Fisher Information Matrix via Cacoullos-Type Inequalities

Some lower bounds for the variance of a function g of a random vector X are extended to a wider class of distributions. Using these bounds, some useful inequalities for the Fisher information are obtained for convolutions and linear combinations of random variables. Finally, using these inequalities, simple proofs are given of classical characterizations of the normal distribution, under certain restrictions, including the matrix analogue of the Darmois-Skitovich result.     

PROBABILISTIC OSTROWSKI TYPE INEQUALITIES

New very general univariate and multivariate probabilistic Ostrowski type inequalities are established, involving ‖·‖_∞ and ‖·‖ _p , p≥1 norms of probability density functions. Some of these inequalities provide pointwise estimates to the error of probability distribution function from the expectation of some simple function of the engaged random variable. Other inequalities give upper bounds for the expectation and variance of a random variable. All are done over finite domains. At the end are given applications, especially for the Beta random variable.     

Concavity and efficient points of discrete distributions in probabilistic programming

We consider stochastic programming problems with probabilistic constraints involving integer-valued random variables. The concept of a p-efficient point of a probability distribution is used to derive various equivalent problem formulations. Next we introduce the concept of r-concave discrete probability distributions and analyse its relevance for problems under consideration. These notions are used to derive lower and upper bounds for the optimal value of probabilistically constrained stochastic programming problems with discrete random variables. The results are illustrated with numerical examples. Received: October 1998 / Accepted: June 2000?Published online October 18, 2000     

Random vectors satisfying Khinchine–Kahane type inequalities for linear and quadratic forms

We study the behaviour of moments of order p (1 < p < ∞) of affine and quadratic forms with respect to non log‐concave measures and we obtain an extension of Khinchine–Kahane inequality for new families of random vectors by using Pisier's inequalities for martingales. As a consequence, we get some estimates for the moments of affine and quadratic forms with respect to a tail volume of the unit ball of lⁿ_q (0 < q < 1). (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Clarkson and Random Clarkson Inequalities for Lr(X)

We first show how (p,p′) Clarkson inequality for a Banach space X is inherited by Lebesgue-Bochner spaces L_r(X), which extends Clarkson's procedure deriving his inequalities for L_p from their scalar versions. Fairly many previous and new results on Clarkson's inequalities, and also those on Rademacher type and cotype at the same time (by a recent result of the authors), are obtained as immediate consequences. Secondly we show that if the (p, p') Clarkson inequality holds in X, then random Clarkson inequalities hold in L_r(X) for any 1 ≤ r ≤ ∞; the converse is true if r = p'. As corollaries the original Clarkson and random Clarkson inequalities for L_p are both directly derived from the parallelogram law for scalars.     

Dimension Free and Infinite Variance Tail Estimates on Poisson Space

Concentration inequalities are obtained on Poisson space, for random functionals with finite or infinite variance. In particular, dimension free tail estimates and exponential integrability results are given for the Euclidean norm of vectors of independent functionals. In the finite variance case these results are applied to infinitely divisible random variables such as quadratic Wiener functionals, including Lévy’s stochastic area and the square norm of Brownian paths. In the infinite variance case, various tail estimates such as stable ones are also presented.      

Reversible coagulation–fragmentation processes and random combinatorial structures: Asymptotics for the number of groups

The equilibrium distribution of a reversible coagulation‐fragmentation process (CFP) and the joint distribution of components of a random combinatorial structure (RCS) are given by the same probability measure on the set of partitions. We establish a central limit theorem for the number of groups (= components) in the case a(k) = qk^p?1, k ≥ 1, q, p > 0, where a(k), k ≥ 1, is the parameter function that induces the invariant measure. The result obtained is compared with the ones for logarithmic RCS's and for RCS's, corresponding to the case p < 0. © 2004 Wiley Periodicals, Inc. Random Struct. Alg. 2004     

Approximations and Inequalities for Moving Sums

In this article accurate approximations and inequalities are derived for the distribution, expected stopping time and variance of the stopping time associated with moving sums of independent and identically distributed continuous random variables. Numerical results for a scan statistic based on a sequence of moving sums are presented for a normal distribution model, for both known and unknown mean and variance. The new R algorithms for the multivariate normal and t distributions established by Genz et?al. (2010) provide readily available numerical values of the bounds and approximations.     

Tail bounds for occupancy and the satisfiability threshold conjecture

The classical occupancy problem is concerned with studying the number of empty bins resulting from a random allocation of m balls to n bins. We provide a series of tail bounds on the distribution of the number of empty bins. These tail bounds should find application in randomized algorithms and probabilistic analysis. Our motivating application is the following well-known conjecture on threshold phenomenon for the satisfiability problem. Consider random 3-SAT formulas with cn clauses over n variables, where each clause is chosen uniformly and independently from the space of all clauses of size 3. It has been conjectured that there is a sharp threshold for satisfiability at c* ≈? 4.2. We provide a strong upper bound on the value of c*, showing that for c > 4.758 a random 3-SAT formula is unsatisfiable with high probability. This result is based on a structural property, possibly of independent interest, whose proof needs several applications of the occupancy tail bounds.     

An Inequality for Large Deviation Probabilities of Sums of Bounded i.i.d. Random Variables

We provide precise bounds for tail probabilities, say {M _n x}, of sums M _n of bounded i.i.d. random variables. The bounds are expressed through tail probabilities of sums of i.i.d. Bernoulli random variables. In other words, we show that the tails are sub-Bernoullian. Sub-Bernoullian tails are dominated by Gaussian tails. Possible extensions of the methods are discussed.     

Poisson approximation for large deviations

Upper and lower bounds are given for P(S ≤ k), 0 ≤ k ≤ ES, where S is a sum of indicator variables with a special structure, which appears, for example, in subgraph counts in random graphs. in typical cases, these bounds are close to the corresponding probabilities for a Poisson distribution with the same mean as S. There are no corresponding general bounds for P(S ≥ k), k > ES, but some partial results are given.     

The correlation bell inequalities

We consider the Bell and Bell-Clauser-Horne-Shimony-Holt inequalities for two-particle spin states. It is known that these inequalities are violated in experimental verification. We show that this can be explained because these inequalities are proved for correlation functions of random variables that are totally unrelated to one another, while the verification is done using correlation functions in which random variables refer to a pair of particles forming a two-particle state. In the case of entangled states, these random functions are dependent, and their correlation coefficient is nonzero. We give inequalities that explicitly involve this correlation coefficient. For factorable and separable states, these inequalities coincide with the standard Bell and Bell-Clauser-Horne-Shimony-Holt inequalities. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 158, No. 2, pp. 234–249, February, 2009.     

关于离散信源的若干强极限定理

本文研究了离散信源广义熵定理以及随机条件概率的广义调和平均a.s.收敛性,在证明中提出了将Markov不等式、Borel-Cantelli引理和随机条件矩母函数等工具应用于强极限定理的研究的一种途径.     

Rosenthal type inequalities for asymptotically almost negatively associated random variables and applications

In this paper, we establish some Rosenthal type inequalities for maximum partial sums of asymptotically almost negatively associated random variables, which extend the corresponding results for negatively associated random variables. As applications of these inequalities, by employing the notions of residual Cesàro α-integrability and strong residual Cesàro α-integrability, we derive some results on L _p convergence where 1 < p < 2 and complete convergence. In addition, we estimate the rate of convergence in Marcinkiewicz-Zygmund strong law for partial sums of identically distributed random variables.     

The lower tail: Poisson approximation revisited

The well‐known “Janson's inequality” gives Poisson‐like upper bounds for the lower tail probability when X is the sum of dependent indicator random variables of a special form. We show that, for large deviations, this inequality is optimal whenever X is approximately Poisson, i.e., when the dependencies are weak. We also present correlation‐based approaches that, in certain symmetric applications, yield related conclusions when X is no longer close to Poisson. As an illustration we, e.g., consider subgraph counts in random graphs, and obtain new lower tail estimates, extending earlier work (for the special case ) of Janson, ?uczak and Ruciński. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 219–246, 2016     

Exponential tail estimates in the law of ordinary logarithm (LOL) for triangular arrays of random variables

We derive exponential bounds for the tail of the distribution of normalized sums of triangular arrays of random variables, not necessarily independent, under the law of ordinary logarithm.

Furthermore, we provide estimates for partial sums of triangular arrays of independent random variables belonging to suitable grand Lebesgue spaces and having heavy-tailed distributions.

     

Addendum to “An extension of an inequality of Hoeffding to unbounded random variables”: The non-i.i.d. case

Let S _n = X ₁ + ⋯ + X _n be a sum of independent random variables such that 0 ⩽ X _k ⩽ 1 for all k. Write {ie237-01} and q = 1 − p. Let 0 < t < q. In our recent paper [3], we extended the inequality of Hoeffding ([6], Theorem 1) {fx237-01} to the case where X _k are unbounded positive random variables. It was assumed that the means {ie237-02} of individual summands are known. In this addendum, we prove that the inequality still holds if only an upper bound for the mean {ie237-03} is known and that the i.i.d. case where {ie237-04} dominates the general non-i.i.d. case. Furthermore, we provide upper bounds expressed in terms of certain compound Poisson distributions. Such bounds can be more convenient in applications. Our inequalities reduce to the related Hoeffding inequalities if 0 ⩽ X _k ⩽ 1. Our conditions are X _k ⩾ 0 and {ie237-05}. In particular, X _k can have fat tails. We provide as well improvements comparable with the inequalities in Bentkus [2]. The independence of X _k can be replaced by super-martingale type assumptions. Our methods can be extended to prove counterparts of other inequalities in Hoeffding [6] and Bentkus The research was partially supported by the Lithuanian State Science and Studies Foundation, grant No T-25/08.     

Bernstein–Nikolskii and Plancherel–Polya inequalities in Lp ‐norms on non‐compact symmetric spaces

By using Bernstein‐type inequality we define analogs of spaces of entire functions of exponential type in L_p (X), 1 ≤ p ≤ ∞, where X is a symmetric space of non‐compact. We give estimates of L_p ‐norms, 1 ≤ p ≤ ∞, of such functions (the Nikolskii‐type inequalities) and also prove the L_p ‐Plancherel–Polya inequalities which imply that our functions of exponential type are uniquely determined by their inner products with certain countable sets of measures with compact supports and can be reconstructed from such sets of “measurements” in a stable way (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Evolving sets, mixing and heat kernel bounds

We show that a new probabilistic technique, recently introduced by the first author, yields the sharpest bounds obtained to date on mixing times of Markov chains in terms of isoperimetric properties of the state space (also known as conductance bounds or Cheeger inequalities). We prove that the bounds for mixing time in total variation obtained by Lovász and Kannan, can be refined to apply to the maximum relative deviation |pⁿ(x,y)/π(y)−1| of the distribution at time n from the stationary distribution π. We then extend our results to Markov chains on infinite state spaces and to continuous-time chains. Our approach yields a direct link between isoperimetric inequalities and heat kernel bounds; previously, this link rested on analytic estimates known as Nash inequalities.Research supported in part by NSF Grants #DMS-0104073 and #DMS-0244479.     

The expectation and variance of the joint linear complexity of random periodic multisequences

The linear complexity of sequences is one of the important security measures for stream cipher systems. Recently, in the study of vectorized stream cipher systems, the joint linear complexity of multisequences has been investigated. By using the generalized discrete Fourier transform for multisequences, Meidl and Niederreiter determined the expectation of the joint linear complexity of random N-periodic multisequences explicitly. In this paper, we study the expectation and variance of the joint linear complexity of random periodic multisequences. Several new lower bounds on the expectation of the joint linear complexity of random periodic multisequences are given. These new lower bounds improve on the previously known lower bounds on the expectation of the joint linear complexity of random periodic multisequences. By further developing the method of Meidl and Niederreiter, we derive a general formula and a general upper bound for the variance of the joint linear complexity of random N-periodic multisequences. These results generalize the formula and upper bound of Dai and Yang for the variance of the linear complexity of random periodic sequences. Moreover, we determine the variance of the joint linear complexity of random periodic multisequences with certain periods.