Inequalities for sums of independent geometrical random variables

Summary We give a survey of known results regarding Schur-convexity of probability distribution functions. Then we prove that the functionF(p ₁,...,p_n;t)=P(X₁+...+X_n≤t) is Schur-concave with respect to (p ₁,...,p_n) for every realt, whereX _i are independent geometric random variables with parametersp _i. A generalization to negative binomial random variables is also presented.     

An application of prophet regions to optimal stopping with a random number of observations

Let X ₁,X ₂ ,?…?be any sequence of nonnegative integrable random variables, and let N∈{1,2 , …} be a random variable with known distribution, independent of X ₁,X ₂ , …. The optimal stopping value sup _t E(X_t I(N≥ t)) is considered for two players: one who has advance knowledge of the value of N, and another who does not. Sharp ratio and difference inequalities relating the two players' optimal values are given in a number of settings. The key to the proofs is an application of a prophet region for arbitrarily dependent random variables by Hill and Kertz [T.P. Hill and R.P. Kertz (1983). Stop rule inequalities for uniformly bounded sequences of random variables. Trans. Amer. Math. Soc., 278, 197–207].     

Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1.

Consider the random graph on n vertices 1,…,n. Each vertex i is assigned a type x_i with x₁,…,x_n being independent identically distributed as a nonnegative random variable X. We assume that EX³< ∞. Given types of all vertices, an edge exists between vertices i and j independent of anything else and with probability \begin{align*}\min \{1, \frac{x_ix_j}{n}\left(1+\frac{a}{n^{1/3}} \right) \}\end{align*}. We study the critical phase, which is known to take place when EX² = 1. We prove that normalized by n^‐2/3the asymptotic joint distributions of component sizes of the graph equals the joint distribution of the excursions of a reflecting Brownian motion with diffusion coefficient \begin{align*}\sqrt{{\textbf{ E}}X{\textbf{ E}}X^3}\end{align*}and drift \begin{align*}a-\frac{{\textbf{ E}}X^3}{{\textbf{ E}}X}s\end{align*}. In particular, we conclude that the size of the largest connected component is of order n^2/3. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 43, 486–539, 2013     

On the Expected Number of Shadow Vertices of the Convex Hull of Random Points

Leta₁, . . . ,a_mbe independent random points in ⁿthat are independent and identically distributed spherically symmetrical in ⁿ. Moreover, letXbe the random polytope generated as the convex hull ofa₁, . . . ,a_mand letL_kbe an arbitraryk-dimensional subspace of ⁿwith 2 ≤k≤n− 1. LetX_kbe the orthogonal projection image ofXinL_k. We call those vertices ofXwhose projection images inL_kare vertices ofX_kshadow vertices ofXwith respect to the subspaceL_k. We derive a distribution independent sharp upper bound for the expected number of shadow vertices ofXinL_k.     

On the average number of records for sequences of not identically distributed random variables

The scheme of n series of independent random variables X ₁₁, X ₂₁, …, X _k1, X ₁₂, X ₂₂, …, X _k2, …, X _1n , X _2n , …, X _kn is considered. Each of these successive series X _1m , X _2m , …, X _km , m = 1, 2, …, n consists of k variables with continuous distribution functions F ₁, F ₂, …, F _k , which are the same for all series. Let N(nk) be the number of upper records of the given nk random variables, and EN(nk) be the corresponding expected value. For EN(nk) exact upper and lower estimates are obtained. Examples are given of the sets of distribution functions for which these estimates are attained.     

On Hamilton cycles in Erdős‐Rényi subgraphs of large graphs

Given a graph Γ_n=(V,E) on n vertices and m edges, we define the Erd?s‐Rényi graph process with host Γ_n as follows. A permutation e₁,…,e_m of E is chosen uniformly at random, and for t ≤ m we let Γ_n,t=(V,{e₁,…,e_t}). Suppose the minimum degree of Γ_n is δ(Γ_n) ≥ (1/2+ε)n for some constant ε>0. Then with high probability (An event holds with high probability (whp) if as n→∞.), Γ_n,t becomes Hamiltonian at the same moment that its minimum degree reaches 2. Given 0 ≤ p ≤ 1 let Γ_n,p be the Erd?s‐Rényi subgraph of Γ_n, obtained by retaining each edge independently with probability p. When δ(Γ_n) ≥ (1/2+ε)n, we provide a threshold for Hamiltonicity in Γ_n,p.     

Large deviations for heavy-tailed random sums of independent random variables with dominatedly varying tails

We prove large deviation results on the partial and random sums Sn = ∑i=1n Xi,n≥1; S(t) = ∑i=1N(t) Xi, t≥0, where {N(t);t≥0} are non-negative integer-valued random variables and {Xn;n≥1} are independent non-negative random variables with distribution, Fn, of Xn, independent of {N(t); t≥0}. Special attention is paid to the distribution of dominated variation.     

Some Remarks on the Number of Solutions to the Equation f(X1) + … + f(Xn) = 0

Let S, T be finite sets, and let f be a function from S to T. Fix an element t in T, and let c_n denote the number of n-tuples (X₁,…,X_n) satisfying f(X₁) + … + f(X_n) = t here + denotes any binary operation on T. The sequence c₁, c₂,… satisfies a linear recurrence relation of degree at most |T|.     

The diameter of randomly perturbed digraphs and some applications

The central observation of this paper is that if εn random arcs are added to any n‐node strongly connected digraph with bounded degree then the resulting graph has diameter 𝒪(lnn) with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 𝔻_n,ε/n we obtain a “smoothed” instance. We show that, with high probability, a log‐space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if NL ⫅̸ almost‐L then no heuristic can recognize similarly perturbed instances of (s,t)‐connectivity. Property Testing: A digraph is called k‐linked if, for every choice of 2k distinct vertices s₁,…,s_k,t₁,…,t_k, the graph contains k vertex disjoint paths joining s_r to t_r for r = 1,…,k. Recognizing k‐linked digraphs is NP‐complete for k ≥ 2. We describe a polynomial time algorithm for bounded degree digraphs, which accepts k‐linked graphs with high probability, and rejects all graphs that are at least εn arcs away from being k‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Group of units of group algebras

By a right (left resp.) S_2n-polynomial we mean a multilinear polynomial f(X₁,…, X_t) over the ring of integers with noncommuting in-determinates X_isuch that for any prime ring R if f( X₁,…, X _t) is a PI of some nonzero right (left resp.) ideal of R, then R satisfies S_2nthe standard identity of degree 2n. In this paper we prove the theorem:Let R be a prime ring, d a nonzero derivation of R, L a noncommutative Lie ideal of R and f(X₁,…, X_t) a right or left S_2n-polynomial. Suppose that f(d( u₁)ⁿ¹,…,d(u_t)^nt)=0 for all u_iu,_i[d] L, where n₁,…,n_tare fixed positive integers. Then R satisfies S_2n+2. Also, the one-sided version of the theorem is given.     

Convergence in distribution of quotients of order statistics

Let X₁, X₂,… be i.i.d. random variables with continuous distribution function F < 1. It is known that if 1 - F(x) varies regularly of order - p, the successive quotients of the order statistics in decreasing order of X₁,…,X_n are asymptotically independent, as n→∞, with distribution functions x^kp, k = 1, 2, …. A strong converse is proved, viz. convergence in distribution of this type of one of the quotients implies regular varation of 1 - F(x).     

Three characterizations of non-binary correlation-immune and resilient functions

A functionf(X ₁,X ₂, ...,X _n ) is said to betth-order correlation-immune if the random variableZ=f(X ₁,X ₂,...,X _n ) is independent of every set oft random variables chosen from the independent equiprobable random variablesX ₁,X ₂,...,X _n . Additionally, if all possible outputs are equally likely, thenf is called at-resilient function. In this paper, we provide three different characterizations oft th-order correlation immune functions and resilient functions where the random variable is overGF (q). The first is in terms of the structure of a certain associated matrix. The second characterization involves Fourier transforms. The third characterization establishes the equivalence of resilient functions and large sets of orthogonal arrays.     

Joint distributions associated with patterns,successes and failures in a sequence of multi-state trials

Let {Z _t ,t≥1} be a sequence of trials taking values in a given setA={0, 1, 2,...,m}, where we regard the value 0 as failure and the remainingm values as successes. Let ε be a (single or compound) pattern. In this paper, we provide a unified approach for the study of two joint distributions, i.e., the joint distribution of the numberX _n of occurrences of ε, the numbers of successes and failures inn trials and the joint distribution of the waiting timeT _r until ther-th occurrence of ε, the numbers of successes and failures appeared at that time. We also investigate some distributions as by-products of the two joint distributions. Our methodology is based on two types of the random variablesX _n (a Markov chain imbeddable variable of binomial type and a Markov chain imbeddable variable of returnable type). The present work develops several variations of the Markov chain imbedding method and enables us to deal with the variety of applications in different fields. Finally, we discuss several practical examples of our results. This research was partially supported by the ISM Cooperative Research Program (2002-ISM·CRP-2007).     

The existence and regularity of multiple solutions for a class of infinitely degenerate elliptic equations

Let X = (X₁, …, X_m) be an infinitely degenerate system of vector fields. We study the existence and regularity of multiple solutions of the Dirichlet problem for a class of semi‐linear infinitely degenerate elliptic operators associated with the sum of square operator δ_X = ∑_{j = 1}^m X_j^* X_j (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Definition and characterization of multivariate negative binomial distribution

The probability generating function (pgf) of an n-variate negative binomial distribution is defined to be [β(s₁,…,s_n)]^?k where β is a polynomial of degree n being linear in each s_i and k > 0. This definition gives rise to two characterizations of negative binomial distributions. An n-variate linear exponential distribution with the probability function h(x₁,…,x_n)$\text{exp}\text{(}\text{Σ}{}_{\mathrm{i=1}}{}^{\mathrm{n}}\text{θ}{}_{\mathrm{i}}\text{x}{}_{\mathrm{i}}\text{)}\text{f(θ}{}_1\text{,…,θ}{}_{\mathrm{n}}\text{)}$ is negative binomial if and only if its univariate marginals are negative binomial. Let S_t, t = 1,…, m, be subsets of {s₁,…, s_n} with empty ∩_t=1^mS_t. Then an n-variate pgf is of a negative binomial if and only if for all s in S_t being fixed the function is of the form of the pgf of a negative binomial in other s's and this is true for all t.     

The structure and distances in Yule recursive trees

Based on uniform recursive trees, we introduce random trees with the factor of time, which are named Yule recursive trees. The structure and the distance between the vertices in Yule recursive trees are investigated in this paper. For arbitrary time t > 0, we first give the probability that a Yule recursive tree Y_t is isomorphic to a given rooted tree γ; and then prove that the asymptotic distribution of ζ_t,m, the number of the branches of size m, is the Poisson distribution with parameter λ = 1/m. Finally, two types of distance between vertices in Yule recursive trees are studied, and some limit theorems for them are established.© 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Nonparametric estimation of mixed partial derivatives of a multivariate density

On the basis of a random sample of size n on an m-dimensional random vector X, this note proposes a class of estimators f_n^(p) of f^(p), where f is a density of X w.r.t. a σ-finite measure dominated by the Lebesgue measure on R^m, p = (p₁,…,p_m), p_j ≥ 0, fixed integers, and for x = (x₁,…,x_m) in R^m, f^(p)(x) = ?^p₁+…+p_m f(x)/(?^p₁x₁ … ?^p_mx_m). Asymptotic unbiasedness as well as both almost sure and mean square consistencies of f_n^(p) are examined. Further, a necessary and sufficient condition for uniform asymptotic unbisedness or for uniform mean square consistency of f_n^(p) is given. Finally, applications of estimators of this note to certain statistical problems are pointed out.     

A certain generalization of the law of the iterated logarithm

Let X₁ ,..., X_n be independent random variables and let \(S_n = \sum\limits_{i = 1}^n {X_i }\) . For the sequence of random variables $$T_n = \sum\limits_1^p {(S_{t_j } - S_{t_{j - 1} } )} ,$$ where t₀=01<...p=n, p?1, under certain conditions on t_i, \(i = \overline {1,n}\) , one proves a series of general theorems of the type of the iterated logarithm laws.     

Quasi‐randomness of graph balanced cut properties

Quasi‐random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, Shapira and Yuster proved the following result on quasi‐randomness of graphs. Let k ≥ 2 be a fixed integer, α₁,…,α_k be positive reals satisfying \begin{align*}\sum_{i} \alpha_i = 1\end{align*} and (α₁,…,α_k)≠(1/k,…,1/k), and G be a graph on n vertices. If for every partition of the vertices of G into sets V ₁,…,V _k of size α₁n,…,α_kn, the number of complete graphs on k vertices which have exactly one vertex in each of these sets is similar to what we would expect in a random graph, then the graph is quasi‐random. However, the method of quasi‐random hypergraphs they used did not provide enough information to resolve the case (1/k,…,1/k) for graphs. In their work, Shapira and Yuster asked whether this case also forces the graph to be quasi‐random. Janson also posed the same question in his study of quasi‐randomness under the framework of graph limits. In this paper, we positively answer their question. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011