Search

The converse of the Borel–Cantelli Lemma states that if { A i } i = 1 ∞ is a sequence of independent events such that ∑ P ( A i ) = ∞ , then almost surely infinitely many of these events will occur. Erdős and Renyi proved that it is sufficient to weaken the condition of independence to pairwise independence. Later, several other weakenings of the condition appeared in the literature. The aim of this paper is to provide a collection of conditions, all of which imply that almost surely infinitely many of the events occur, and determine the complete implicational relationship between them. Many of these results are known, or follow from known results, however, they are not widely known among non-specialists. Yet, the results can be extremely useful for areas outside of probability theory, as evidenced by the original motivation of this paper emerging from infinite combinatorics. Our proofs are aimed to be accessible to a general mathematical audience.

Accurately capturing the dependence between risks, if it exists, is an increasingly relevant topic of actuarial research. In recent years, several authors have started to relax the traditional 'independence assumption', in a variety of actuarial settings. While it is known that 'mutual independence' between random variables is not equivalent to their 'pairwise independence', this thesis aims to provide a better understanding of the materiality of this difference. The distinction between mutual and pairwise independence matters because, in practice, dependence is often assessed via pairs only, e.g., through correlation matrices, rank-based measures of association, scatterplot matrices, heat-maps, etc. Using such pairwise methods, it is possible to miss some forms of dependence. In this thesis, we explore how material the difference between pairwise and mutual independence is, and from several angles. We provide relevant background and motivation for this thesis in Chapter 1, then conduct a literature review in Chapter 2. In Chapter 3, we focus on visualising the difference between pairwise and mutual independence. To do so, we propose a series of theoretical examples (some of them new) where random variables are pairwise independent but (mutually) dependent, in short, PIBD. We then develop new visualisation tools and use them to illustrate what PIBD variables can look like. We showcase that the dependence involved is possibly very strong. We also use our visualisation tools to identify subtle forms of dependence, which would otherwise be hard to detect. In Chapter 4, we review common dependence models (such has elliptical distributions and Archimedean copulas) used in actuarial science and show that they do not allow for the possibility of PIBD data. We also investigate concrete consequences of the 'nonequivalence' between pairwise and mutual independence. We establish that many results which hold for mutually independent variables do not hold under sole pairwise independent. Those include results about finite sums of random variables, extreme value theory and bootstrap methods. This part thus illustrates what can potentially 'go wrong' if one assumes mutual independence where only pairwise independence holds. Lastly, in Chapters 5 and 6, we investigate the question of what happens for PIBD variables 'in the limit', i.e., when the sample size goes to infi nity. We want to see if the 'problems' caused by dependence vanish for sufficiently large samples. This is a broad question, and we concentrate on the important classical Central Limit Theorem (CLT), for which we fi nd that the answer is largely negative. In particular, we construct new sequences of PIBD variables (with arbitrary margins) for which a CLT does not hold. We derive explicitly the asymptotic distribution of the standardised mean of our sequences, which allows us to illustrate the extent of the 'failure' of a CLT for PIBD variables. We also propose a general methodology to construct dependent K-tuplewise independent (K an arbitrary integer) sequences of random variables with arbitrary margins. In the case K = 3, we use this methodology to derive explicit examples of triplewise independent sequences for which no CLT hold. Those results illustrate that mutual independence is a crucial assumption within CLTs, and that having larger samples is not always a viable solution to the problem of non-independent data.

This paper proves the Baum--Katz theorem for sequences of pairwise independent identically distributed random variables with general norming constants under optimal moment conditions. The proof exploits some properties of slowly varying functions and the de Bruijn conjugates, and uses the techniques developed by Rio (1995) to avoid using the maximal type inequalities., Comment: Comptes Rendus Math\'{e}matique, 358, 2020, 1231--1238. A typo at the last line of equation (34) in the journal version is corrected

We consider a linear discrete time-varying system with multiplicative noise acted upon by colored exogenous disturbance with nonzero first moment. Multiplicative noises are modeled in the form of linear combinations of deterministic matrices with pairwise independent random coefficients. For this system, we describe a method, based on a state-space realization, for calculating the anisotropic norm in terms of Riccati equations.

In cluster physics, the determination of the ground-state structure of medium-sized and large-sized clusters is a challenge due to the number of local minimal values on the potential energy surface growing exponentially with cluster size. Although machine learning approaches have had much success in materials sciences, their applications in clusters are often hindered by the geometric complexity clusters. Persistent homology provides a new topological strategy to simplify geometric complexity while retaining important chemical and physical information without having to "downgrade" the original data. We further propose persistent pairwise independence (PPI) to enhance the predictive power of persistent homology. We construct topology-based machine learning models to reveal hidden structure-energy relationships in lithium (Li) clusters. We integrate the topology-based machine learning models, a particle swarm optimization algorithm, and density functional theory calculations to accelerate the search of the globally stable structure of clusters.

We obtain the necessary and sufficient conditions for the stability in the quadratic mean of strong solutions to stochastic partial differential-difference equations with pairwise independent external random perturbations of the type of random variables.

We establish new sufficient conditions for the applicability of the strong law of large numbers (SLLN) for sequences of pairwise independent, nonidentically distributed random variables. These results generalize Etemadi’s extension of Kolmogorov’s SLLN for identically distributed random variables. Some of the obtained results hold with an arbitrary norming sequence in place of the classical normalization.

We continue the study of covering complexity of constraint satisfaction problems (CSPs) initiated by Guruswami, Hastad and Sudan [SIAM J. Computing, 31(6):1663--1686, 2002] and Dinur and Kol [In Proc. $28$th IEEE Conference on Computational Complexity, 2013]. The covering number of a CSP instance $\Phi$, denoted by $\nu(\Phi)$ is the smallest number of assignments to the variables of $\Phi$, such that each constraint of $\Phi$ is satisfied by at least one of the assignments. We show the following results regarding how well efficient algorithms can approximate the covering number of a given CSP instance. - Assuming a covering unique games conjecture, introduced by Dinur and Kol, we show that for every non-odd predicate $P$ over any constant sized alphabet and every integer $K$, it is NP-hard to distinguish between $P$-CSP instances (i.e., CSP instances where all the constraints are of type $P$) which are coverable by a constant number of assignments and those whose covering number is at least $K$. Previously, Dinur and Kol, using the same covering unique games conjecture, had shown a similar hardness result for every non-odd predicate over the Boolean alphabet that supports a pairwise independent distribution. Our generalization yields a complete characterization of CSPs over constant sized alphabet $\Sigma$ that are hard to cover since CSP's over odd predicates are trivially coverable with $|\Sigma|$ assignments. - For a large class of predicates that are contained in the $2k$-LIN predicate, we show that it is quasi-NP-hard to distinguish between instances which have covering number at most two and covering number at least $\Omega(\log\log n)$. This generalizes the $4$-LIN result of Dinur and Kol that states it is quasi-NP-hard to distinguish between $4$-LIN-CSP instances which have covering number at most two and covering number at least $\Omega(\log \log\log n)$.

We propose a key-policy attribute-based encryption (KP-ABE) scheme with constant-size ciphertexts, whose selective security is proven under the decisional linear (DLIN) assumption in the standard model. The proposed scheme also has semi-adaptively security, which is a recently proposed notion of security. The access structure is expressive, that is given by non-monotone span programs. It also has fast decryption, i.e., a decryption includes only a constant number of pairing operations. As an application of our KP-ABE construction, we also propose a fully secure attribute-based signatures with constant-size secret (signing) keys from the DLIN. For achieving the above results, we employ a hierarchical reduction technique on dual pairing vector spaces and a modified form of pairwise independence lemma specific to our proposed schemes.

Distance multivariance is a multivariate dependence measure, which can detect dependencies between an arbitrary number of random vectors each of which can have a distinct dimension. Here we discuss several new aspects, present a concise overview and use it as the basis for several new results and concepts: In particular, we show that distance multivariance unifies (and extends) distance covariance and the Hilbert-Schmidt independence criterion HSIC, moreover also the classical linear dependence measures: covariance, Pearson's correlation and the RV coefficient appear as limiting cases. Based on distance multivariance several new measures are defined: a multicorrelation which satisfies a natural set of multivariate dependence measure axioms and $m$-multivariance which is a dependence measure yielding tests for pairwise independence and independence of higher order. These tests are computationally feasible and under very mild moment conditions they are consistent against all alternatives. Moreover, a general visualization scheme for higher order dependencies is proposed, including consistent estimators (based on distance multivariance) for the dependence structure. Many illustrative examples are provided. All functions for the use of distance multivariance in applications are published in the R-package 'multivariance'., Comment: restructured; several new results

This paper discusses joint rectangular chance or probabilistic constrained geometric programs. We present a new reformulation of the joint rectangular chance constrained geometric programs where the random parameters are elliptically distributed and pairwise independent. As this reformulation is not convex, we propose new convex approximations based on the variable transformation together with piecewise linear approximation methods. For the latter, we provide a theoretical bound for the number of segments in the worst case. Our numerical results show that our approximations are asymptotically tight.

Unsupervised disentangled representation learning is one of the foundational methods to learn interpretable factors in the data. Existing learning methods are based on the assumption that disentangled factors are mutually independent and incorporate this assumption with the evidence lower bound. However, our experiment reveals that factors in real-world data tend to be pairwise independent. Accordingly, we propose a new method based on a pairwise independence assumption to learn the disentangled representation. The evidence lower bound implicitly encourages mutual independence of latent codes so it is too strong for our assumption. Therefore, we introduce another lower bound in our method. Extensive experiments show that our proposed method gives competitive performances as compared with other state-of-the-art methods.

In a recent Letter [Phys. Rev. Lett. 122, 010403 (2019)], an equivalence is proposed between the so-called Spectrum Broadcast Structure for a system-multienvironment quantum state, and the conjunction of two information-theory notions: (a) Strong Quantum Darwinism; and (b) Strong Independence. Here, we show that the mathematical formulation of condition (b) by the authors (namely, the pairwise independence of the fragments of the environment, conditioned on the system), is necessary but not sufficient to ensure the equivalence. We propose a simple counter-example, together with a strengthened formulation of condition (b), ensuring the equivalence proposed by the authors., 2 pages, no figure

A general parameter process defined by a continuum of random variables is not jointly measurable with respect to the usual product σ-algebra. For the case of independent random variables, a one-way Fubini extension of the product space was constructed in [11] to satisfy a limited form of joint measurability. For the general case we show that this extension exists if and only if there is a countably generated σ-algebra given which the random variables are essentially pairwise conditionally independent, while their joint conditional distribution also satisfies a suitable joint measurability condition. Applications include new characterizations of essential pairwise independence and essential pairwise exchangeability through regular conditional distributions with respect to the usual product σ-algebra in the framework of a one-way Fubini extension.

The exact lower bound on the probability of the occurrence of exactly one of $n$ random events each of probability $p$ is obtained., Comment: 6 pages; to appear in the Bulletin of the Australian Mathematical Society

Block ciphers such as the Advanced Encryption Standard (Rijndael) are used extensively in practice, yet our understanding of their security continues to be highly incomplete. This paper promotes and continues a research program aimed at proving the security of block ciphers against important and well-studied classes of attacks. In particular, we initiate the study of (almost) t-wise independence of concrete block-cipher construction paradigms such as substitution-permutation networks and key-alternating ciphers. Sufficiently strong (almost) pairwise independence already suffices to resist (truncated) differential attacks and linear cryptanalysis, and hence this is a relevant and meaningful target. Our results are two-fold.

In the previous chapter we looked at dedicated forms of hash functions that we categorized as non-cryptographic hash functions. Their common denominator is that we can prove the existence of constructions that fulfill the properties (e.g., pairwise independence) without having to rely on unproven assumptions.

Random elements and processes, finite-dimensional distributions, expectation and covariance, moments and tails, Jensen’s inequality, independence, pairwise independence and grouping, product measures and convolution, iterated expectation, Kolmogorov and Hewitt–Savage 0−1 laws, Borel–Cantelli lemma, replication and Bernoulli sequences, kernel representation, Holder continuity, multi-variate distributions

Testing mutual independence for high-dimensional observations is a fundamental statistical challenge. Popular tests based on linear and simple rank correlations are known to be incapable of detecting nonlinear, nonmonotone relationships, calling for methods that can account for such dependences. To address this challenge, we propose a family of tests that are constructed using maxima of pairwise rank correlations that permit consistent assessment of pairwise independence. Built upon a newly developed Cramér-type moderate deviation theorem for degenerate U-statistics, our results cover a variety of rank correlations including Hoeffding’s $D$, Blum–Kiefer–Rosenblatt’s $R$ and Bergsma–Dassios–Yanagimoto’s $\tau^{*}$. The proposed tests are distribution-free in the class of multivariate distributions with continuous margins, implementable without the need for permutation, and are shown to be rate-optimal against sparse alternatives under the Gaussian copula model. As a by-product of the study, we reveal an identity between the aforementioned three rank correlation statistics, and hence make a step towards proving a conjecture of Bergsma and Dassios.

The discussion rate region in the multiterminal source model is the individual discussion rate required for generating a secret key of maximum rate. We give an explicit single-letter characterization of the discussion rate region for a large class of pairwise independent network (PIN) models. Besides, we also establish a sufficient condition for identifying whether a PIN model belongs to this class, which can be checked in strongly polynomial time. As a by-product, the discussion rate region reduces to a very simple expression for PIN model satisfying such condition.

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 $\mathbf{p} \in [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 \geq 2$ and input marginal probability vector $\mathbf{p} \in [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., 42 pages, 6 figures

In this correspondence, for a nonnegative regular summability matrix B and an array $$\left\{ a_{nk}\right\} $$ of real numbers, the concept of B-statistical uniform integrability of a sequence of random variables $$\left\{ X_{k}\right\} $$ with respect to $$\left\{ a_{nk}\right\} $$ is introduced. This concept is more general and weaker than the concept of $$\left\{ X_{k}\right\} $$ being uniformly integrable with respect to $$\left\{ a_{nk}\right\} $$ . Two characterizations of B-statistical uniform integrability with respect to $$\left\{ a_{nk}\right\} $$ are established, one of which is a de La Vallee Poussin-type characterization. For a sequence of pairwise independent random variables $$\left\{ X_{k}\right\} $$ which is B-statistically uniformly integrable with respect to $$\left\{ a_{nk}\right\} $$ , a law of large numbers with mean convergence in the statistical sense is presented for $$\sum \nolimits _{k=1}^{\infty }a_{nk}(X_{k}-\mathbb {E}X_{k})$$ as $$n\rightarrow \infty $$ . A version is obtained without the pairwise independence assumption by strengthening other conditions.

The Central Limit Theorem (CLT) is one of the most fundamental results in Statistics. It states that the standardized sample mean of a sequence of n mutually independent and identically distributed random variables with finite first and second moments converges in distribution to a standard Gaussian as n goes to infinity. In particular, pairwise independence of the sequence is generally not sufficient for the theorem to hold. In this paper, we review the literature on sequences of random variables that fail to satisfy the conclusion of the CLT. Additionally, we construct explicitly a sequence of pairwise independent random variables having a common but arbitrary marginal distribution $\mathcal{L}$, and for which the CLT is not verified. We study the extent of this 'failure' of the CLT by obtaining, in closed form, the asymptotic distribution of the sample mean of our sequence. It is asymmetric with a tail that is always heavier than that of a Gaussian. It is remarkable that this asymptotic distribution is parametric, its sole parameter being related to the median of $\mathcal{L}$.

This paper provides necessary and sufficient conditions for complete convergence of double weighted sums of pairwise independent identically distributed random elements in Banach spaces. The main theorem extends Theorem 1.2 in [1] to the double weighted sum setting. The sharpness of the main result is illustrated by showing that the main theorem can fail if we replace the identical distribution condition by a slightly weaker condition, even when the random elements are independent and uniformly almost surely bounded.

Intelligent vehicle greatly benefits traffic safety, efficiency and driving comfortable. With the development of intelligent driving technology and its application, it is becoming increasingly important to do effective and comprehensive tests before putting on the market. Comprehensively considering the cost of test, an automatic generation method of test scenarios is proposed to ensure both coverage and effectiveness. Based on the analyzed key infuence factors of an intelligent driving system, the analytic hierarchy process (AHP) is used to determine their importance and accordingly an complex index is defined, based on which an improved test case generation algorithm based on the pairwise independent combinatorial testing tool (PICT) is proposed to ensuring both combinational coverage and complexity of test cases. Finally, the test scenario is generated by clustering these discrete test cases considering similarity and complexity. The high complex test cases are preferred to be combined together and conducted preferentially to increase the test efficiency. The effectiveness of this method is validated by applying it on a lane departure warning system (LDW).

We consider Khintchine type inequalities on the p th moments of vectors of N k -wise independent Rademacher random variables. We show that an analogue of Khintchine’s inequality holds, with a constant N 1 ∕ 2 − k ∕ 2 p , when k is even. We then show that this result is sharp for k = 2 ; in particular, a version of Khintchine’s inequality for sequences of pairwise Rademacher variables cannot hold with a constant independent of N . We also characterize the cases of equality and show that, although the vector achieving equality is not unique, it is unique (up to law) among the smaller class of exchangeable vectors of pairwise independent Rademacher random variables. As a fortunate consequence of our work, we obtain similar results for 3 -wise independent vectors.

Baoding Liu created uncertainty theory to describe the information represented by human language. In turn, Yuhan Liu founded chance theory for modelling phenomena where both uncertainty and randomness are present. The first theory involves an uncertain measure and variable, whereas the second one introduces the notions of a chance measure and an uncertain random variable. Laws of large numbers (LLNs) are important theorems within both theories. In this paper, we prove a law of large numbers (LLN) for uncertain random variables being continuous functions of pairwise independent, identically distributed random variables and regular, independent, identically distributed uncertain variables, which is a generalisation of a previously proved version of LLN, where the independence of random variables was assumed. Moreover, we prove the Marcinkiewicz–Zygmund type LLN in the case of uncertain random variables. The proved version of the Marcinkiewicz–Zygmund type theorem reflects the difference between probability and chance theory. Furthermore, we obtain the Chow type LLN for delayed sums of uncertain random variables and formulate counterparts of the last two theorems for uncertain variables. Finally, we provide illustrative examples of applications of the proved theorems. All the proved theorems can be applied for uncertain random variables being functions of symmetrically or asymmetrically distributed random variables, and symmetrical or asymmetrical uncertain variables. Furthermore, in some special cases, under the assumption of symmetry of the random and uncertain variables, the limits in the first and the third theorem have forms of symmetrical uncertain variables.

In this correspondence, we present new results concerning the concept of stochastic domination and apply them to obtain new results on uniform integrability and on the strong law of large numbers for sequences of pairwise independent random variables. Our result on the strong law of large numbers extends a result of Chen, Bai, and Sung (2014). The sharpness of the results is illustrated by three examples.

The classical Central Limit Theorem (CLT) is one of the most fundamental results in statistics. It states that the standardized sample mean of a sequence of n mutually independent and identically distributed random variables with finite second moment converges in distribution to a standard Gaussian as n goes to infinity. In particular, pairwise independence of the sequence is generally not sufficient for the theorem to hold. We construct explicitly such a sequence of pairwise independent random variables having a common but arbitrary marginal distribution F (satisfying very mild conditions) and for which no CLT holds. We obtain, in closed form, the asymptotic distribution of the sample mean of our sequence, and find it is asymmetrical for any F. This is illustrated through several theoretical examples for various choices of F. Associated R codes are provided in a supplementary appendix online.

The authors develop a framework to select a subset of sensors from a field in which the sensors have an ingrained independence structure. Given an arbitrary independence pattern, the authors construct a graph that denotes pairwise independence between sensors, which means those sensors may operate simultaneously without interfering. The set of all fully-connected subgraphs (cliques) of this independence graph forms the independent sets of matroids over which the authors maximise the average and minimum of a set of submodular objective functions. The average case is submodular, so it can be approximated. The minimum case is both non-submodular and inapproximable. The authors propose a novel algorithm GENSAT that exploits submodularity and, as a result, returns a near-optimal solution with approximation guarantees on a relaxed problem that are within a small factor of the average case scenario. The authors apply this framework to ping sequence optimisation for active multistatic sonar arrays by maximising sensor coverage for average and minimum case scenarios and derive lower bounds for minimum probability of detection for a fractional number of targets. In these ping sequence optimisation simulations, GENSAT exceeds the fractional lower bounds and reaches near-optimal performance, and submodular function optimisation vastly outperforms traditional approaches and nearly achieves optimal performance.

Nadimi et al. (Multidimens Syst Signal Process 2017. https://doi.org/10.1007/s11045-017-0519-3 ) studied the distribution of the ratio of two independent complex Gaussian random variables. The expressions provided for the distribution involved a hypergeometric function and an infinite sum. Here, we derive simpler and more manageable expressions. The practical usefulness of the expressions in terms of computational time is illustrated.