On construction ofk-wise independent random variables

A 0–1probability space is a probability space (, 2,P), where the sample space -{0, 1} ⁿ for somen. A probability space isk-wise independent if, whenY _i is defined to be theith coordinate or the randomn-vector, then any subset ofk of theY _i 's is (mutually) independent, and it is said to be a probability spacefor p ₁,p ₂, ...,p _n ifP[Y _i =1]=p _i .We study constructions ofk-wise independent 0–1 probability spaces in which thep _i 's are arbitrary. It was known that for anyp ₁,p ₂, ...,p _n , ak-wise independent probability space of size always exists. We prove that for somep ₁,p ₂, ...,p _n [0,1],m(n,k) is a lower bound on the size of anyk-wise independent 0–1 probability space. For each fixedk, we prove that everyk-wise independent 0–1 probability space when eachp _i =k/n has size (n _k ). For a very large degree of independence —k=[n], for >1/2- and allp _i =1/2, we prove a lower bound on the size of . We also give explicit constructions ofk-wise independent 0–1 probability spaces.This author was supported in part by NSF grant CCR 9107349.This research was supported in part by the Israel Science Foundation administered by the lsrael Academy of Science and Humanities and by a grant of the Israeli Ministry of Science and Technology.     

The asymptotic number of labeled connected graphs with a given number of vertices and edges

Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n ) edges. Let x = q/n and k = q ? n. We determine functions w_k ? 1. a(x) and φ(x) such that c(n, q) ? w_k(q^N)eⁿφ(x)+a(x) uniformly for all n and q ≥ n. If ? > 0 is fixed, n→ ∞ and 4q > (1 + ?)n log n, this formula simplifies to c(n, q) ? (N^q) exp(–ne^?2q/n). on the other hand, if k = o(n^1/2), this formula simplifies to c(n, n + k) ? 1/2 w_k (3/π)^1/2 (e/12k)^k/2nⁿ?^(3k?1)/2.     

Approximation of monomials by lower degree polynomials

Our topic is the uniform approximation ofx ^k by polynomials of degreen (n on the interval [–1, 1]. Our major result indicates that good approximation is possible whenk is much smaller thann ² and not possible otherwise. Indeed, we show that the approximation error is of the exact order of magnitude of a quantity,p _k,n , which can be identified with a certain probability. The numberp _k,n is in fact the probability that when a (fair) coin is tossedk times the magnitude of the difference between the number of heads and the number of tails exceedsn.     

An Asymptotic Property of Schachermayer's Space under Renorming

Let X be a Banach space with closed unit ball B. Given k , X is said to be k-β, respectively, (k + 1)-nearly uniformly convex ((k + 1)-NUC), if for every ε > 0 there exists δ, 0 < δ < 1, so that for every x B and every ε-separated sequence (x_n) B there are indices (n_i)^k_{i = 1}, respectively, (n_i)^{k + 1}_{i = 1}, such that (1/(k + 1))||x + ∑^k_{i = 1} x_ni|| ≤ 1 − δ, respectively, (1/(k + 1))||∑^{k + 1}_{i = 1} x_ni|| ≤ 1 − δ. It is shown that a Banach space constructed by Schachermayer is 2-β, but is not isomorphic to any 2-NUC Banach space. Modifying this example, we also show that there is a 2-NUC Banach space which cannot be equivalently renormed to be 1-β.     

Volumes Spanned by Random Points in the Hypercube

Consider the hypercube [0, 1]ⁿ in Rⁿ. This has 2ⁿ vertices and volume 1. Pick N = N(n) vertices independently at random, form their convex hull, and let V_n be its expected volume. How large should N(n) be to pick up significant volume? Let k=2/√≈1.213, and let ? > 0. We shall show that, as n→∞, V_n→0 if N(n)?(k??)ⁿ →1 if N(n) ? (k + ?)ⁿ. A similar result holds for sampling uniformly from within the hypercube, with constant .     

Hit-and-run mixes fast

It is shown that the “hit-and-run” algorithm for sampling from a convex body K (introduced by R.L. Smith) mixes in time O ^*(n ² R ²/r ²), where R and r are the radii of the inscribed and circumscribed balls of K. Thus after appropriate preprocessing, hit-and-run produces an approximately uniformly distributed sample point in time O ^*(n ³), which matches the best known bound for other sampling algorithms. We show that the bound is best possible in terms of R,r and n. Received January 26, 1998 / Revised version received October 26, 1998?Published online July 19, 1999     

Legendre polynomial kernel estimation of a density function with censored observations and an application to clinical trials

Let f(x), x ∈ ?^M, M ≥ 1, be a density function on ?^M, and X₁, …., X_n a sample of independent random vectors with this common density. For a rectangle B in ?^M, suppose that the X's are censored outside B, that is, the value X_k is observed only if X_k ∈ B. The restriction of f(x) to x ∈ B is clearly estimable by established methods on the basis of the censored observations. The purpose of this paper is to show how to extrapolate a particular estimator, based on the censored sample, from the rectangle B to a specified rectangle C containing B. The results are stated explicitly for M = 1, 2, and are directly extendible to M ≥ 3. For M = 2, the extrapolation from the rectangle B to the rectangle C is extended to the case where B and C are triangles. This is done by means of an elementary mapping of the positive quarter‐plane onto the strip {(u, v): 0 ≤ u ≤ 1, v > 0}. This particular extrapolation is applied to the estimation of the survival distribution based on censored observations in clinical trials. It represents a generalization of a method proposed in 2001 by the author [2]. The extrapolator has the following form: For m ≥ 1 and n ≥ 1, let K_{m, n}(x) be the classical kernel estimator of f(x), x ∈ B, based on the orthonormal Legendre polynomial kernel of degree m and a sample of n observed vectors censored outside B. The main result, stated in the cases M = 1, 2, is an explicit bound for E|K_{m, n}(x) ? f(x)| for x ∈ C, which represents the expected absolute error of extrapolation to C. It is shown that the extrapolator is a consistent estimator of f(x), x ∈ C, if f is sufficiently smooth and if m and n both tend to ∞ in a way that n increases sufficiently rapidly relative to m. © 2006 Wiley Periodicals, Inc.     

On some characterization of probability distributions in Hilbert spaces

Summary The aim of this paper is to prove the following theorem about characterization of probability distributions in Hilbert spaces:Theorem. — Let x₁, x₂, …, x_n be n (n≥3) independent random variables in the Hilbert spaceH, having their characteristic functionals f_k(t) = E[e^i(t,x _k)], (k=1, 2, …, n): let y₁=x₁ + x_n, y₂=x₂ + x_n, …, y_n−1=x_n−1 + x_n. If the characteristic functional f(t₁, t₂, …, t_n−1) of the random variables (y₁, y₂, …, y_n−1) does not vanish, then the joint distribution of (y₁, y₂, …, y_n−1) determines all the distributions of x₁, x₂, …, x_n up to change of location.     

A note on symbolic and ordinary powers of homogeneous ideals

In this note we are interested in the graded modulesM _k=I^(k)/I^k and , whereI is a saturated ideal in the homogeneous coordinate ringS=K[x₀,…,x_n] of ℙⁿ,I ^(k) is the symbolic power and is the saturation of the ordinary power. Very little is known about these modules, and we provide a bound on their diameters, we compute the Hilbert functions and we study some characteristic submodules in the special case ofn+1 general points in ℙⁿ.

---

Sunto In questa nota siamo interessati ai moduli graduatiM _k=I(k)/I^k e , doveI è un ideale saturato nell'anello delle coordinate omogeneeS:=K[x₀,…,x_n] di ℙⁿ,I ^(k) è la potenza simbolica e è la saturazione della potenza ordinaria. Poco è noto su questi moduli e qui viene fornito un limite superiore ai loro diametri. Ne calcoliamo inoltre le funzioni di Hilbert e studiamo alcuni sottomoduli caratteristici nel caso speciale din+1 punti in posizione generale, in ℙⁿ.

     

Inclusion-exclusion inequalities

Ifμ is a positive measure, andA ₂, ...,A _n are measurable sets, the sequencesS ₀, ...,S _n andP _[0], ...,P _[n] are related by the inclusion-exclusion equalities. Inequalities among theS _i are based on the obviousP _[k]≧0. Letting =the average average measure of the intersection ofk of the setsA _i , it is shown that (−1) ^k Δ ^k M _i ≧0 fori+k≦n. The casek=1 yields Fréchet’s inequalities, andk=2 yields Gumbel’s and K. L. Chung’s inequalities. Generalizations are given involvingk-th order divided differences. Using convexity arguments, it is shown that forS ₀=1, whenS ₁≧N−1, and for 1≦k<N≦n andv=0, 1, .... Asymptotic results asn → ∞ are obtained. In particular it is shown that for fixedN, for all sequencesM ₀, ...,M _n of sufficiently large length if and only if for 0<t<1.     

Large spaces of symmetric matrices of bounded rank are decomposable ∗

Let k and n be positive integers such that kn. Let S_n (F) denote the space of all n×n symmetric matrices over the field F with char F≠2. A subspace L of S_n (F) is said to be a k-subspace if rank Ak for every A?L.

Now suppose that k is even, and write k=2r. We say a k∥-subspace of S_n (F) is decomposable if there exists in Fⁿ a subspace W of dimension n?r such that x^tAx=0 for every x?W A?L.

We show here, under some mild assumptions on k n and F, that every k∥-subspace of S_n (F) of sufficiently large dimension must be decomposable. This is an analogue of a result obtained by Atkinson and Lloyd for corresponding subspaces of F^m,n .     

Coin flipping from a cosmic source: On error correction of truly random bits

We study a problem related to coin flipping, coding theory, and noise sensitivity. Consider a source of truly random bits x ∈ {0, 1}ⁿ, and k parties, who have noisy version of the source bits yⁱ ∈ {0, 1}ⁿ, when for all i and j, it holds that P [y = x_j] = 1 ? ?, independently for all i and j. That is, each party sees each bit correctly with probability 1 ? ?, and incorrectly (flipped) with probability ?, independently for all bits and all parties. The parties, who cannot communicate, wish to agree beforehand on balanced functions f_i: {0, 1}ⁿ → {0, 1} such that P [f₁(y¹) = … = f_k(y^k)] is maximized. In other words, each party wants to toss a fair coin so that the probability that all parties have the same coin is maximized. The function f_i may be thought of as an error correcting procedure for the source x. When k = 2,3, no error correction is possible, as the optimal protocol is given by f_i(yⁱ) = y. On the other hand, for large values of k, better protocols exist. We study general properties of the optimal protocols and the asymptotic behavior of the problem with respect to k, n, and ?. Our analysis uses tools from probability, discrete Fourier analysis, convexity, and discrete symmetrization. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Hermite-Fejér插值的收敛准则

本文给出Hermite-Fejér插值的若干收敛准则.其中之一是:Hermite-Fejer插值算子对每一个连续函数一致收敛当且仅当该算子范数一致有界且该算子对两个单项式x及x²一致收敛.     

Critical behavior in inhomogeneous random graphs

We study the critical behavior of inhomogeneous random graphs in the so‐called rank‐1 case, where edges are present independently but with unequal edge occupation probabilities. The edge occupation probabilities are moderated by vertex weights, and are such that the degree of vertex i is close in distribution to a Poisson random variable with parameter w_i, where w_i denotes the weight of vertex i. We choose the weights such that the weight of a uniformly chosen vertex converges in distribution to a limiting random variable W. In this case, the proportion of vertices with degree k is close to the probability that a Poisson random variable with random parameter W takes the value k. We pay special attention to the power‐law case, i.e., the case where \begin{align*}{\mathbb{P}}(W\geq k)\end{align*} is proportional to k^‐(τ‐1) for some power‐law exponent τ > 3, a property which is then inherited by the asymptotic degree distribution. We show that the critical behavior depends sensitively on the properties of the asymptotic degree distribution moderated by the asymptotic weight distribution W. Indeed, when \begin{align*}{\mathbb{P}}(W > k) \leq ck^{-(\tau-1)}\end{align*} for all k ≥ 1 and some τ > 4 and c > 0, the largest critical connected component in a graph of size n is of order n^2/3, as it is for the critical Erd?s‐Rényi random graph. When, instead, \begin{align*}{\mathbb{P}}(W > k)=ck^{-(\tau-1)}(1+o(1))\end{align*} for k large and some τ∈(3,4) and c > 0, the largest critical connected component is of the much smaller order n^{(τ‐2)/(τ‐1)}. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 480–508, 2013     

On ε‐biased generators in NC0

Cryan and Miltersen (Proceedings of the 26th Mathematical Foundations of Computer Science, 2001, pp. 272–284) recently considered the question of whether there can be a pseudorandom generator in NC⁰, that is, a pseudorandom generator that maps n‐bit strings to m‐bit strings such that every bit of the output depends on a constant number k of bits of the seed. They show that for k = 3, if m ≥ 4n + 1, there is a distinguisher; in fact, they show that in this case it is possible to break the generator with a linear test, that is, there is a subset of bits of the output whose XOR has a noticeable bias. They leave the question open for k ≥ 4. In fact, they ask whether every NC⁰ generator can be broken by a statistical test that simply XORs some bits of the input. Equivalently, is it the case that no NC⁰ generator can sample an ε‐biased space with negligible ε? We give a generator for k = 5 that maps n bits into cn bits, so that every bit of the output depends on 5 bits of the seed, and the XOR of every subset of the bits of the output has bias 2. For large values of k, we construct generators that map n bits to bits such that every XOR of outputs has bias . We also present a polynomial‐time distinguisher for k = 4,m ≥ 24n having constant distinguishing probability. For large values of k we show that a linear distinguisher with a constant distinguishing probability exists once m ≥ Ω(2^kn^?k/2?). Finally, we consider a variant of the problem where each of the output bits is a degree k polynomial in the inputs. We show there exists a degree k = 2 pseudorandom generator for which the XOR of every subset of the outputs has bias 2^?Ω(n) and which maps n bits to Ω(n²) bits. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Random walk in random scenery and self-intersection local times in dimensions d ≥ 5

Let {S _k , k ≥ 0} be a symmetric random walk on , and an independent random field of centered i.i.d. random variables with tail decay . We consider a random walk in random scenery, that is . We present asymptotics for the probability, over both randomness, that {X _n > n ^β} for β > 1/2 and α > 1. To obtain such asymptotics, we establish large deviations estimates for the self-intersection local times process , where l _n (x) is the number of visits of site x up to time n.      

A problem on semigroups satisfying permutation identities

Let σ be a nontrivial permutation of ordern. A semigroupS is said to be σ-permutable ifx ₁ x ₂ ...x _n =x _σ(1) x _σ(2) ...x _σ(n) , for every (x ₁ ,x ₂,...,x _n )∈S ⁿ . A semigroupS is called(r,t)-commutative, wherer,t are in ℕ^*, ifx ₁ ...x _r x _r+1 ...x _r+t =x _r+1 ...x _r+t x ₁ ...x _r , for every (x ₁ ,x ₂,...,x _r+t ∈S ^r+t . According to a result of M. Putcha and A. Yaqub ([11]), if σ is a fixed-point-free permutation andS is a σ-permutable semigroup then there existsk ∈ ℕ^* such thatS is (1,k)-commutative. In [8], S. Lajos raises up the problem to determine the leastk=k(n) ∈ ℕ^* such that, for every fixed-point-free permutation σ of ordern, every σ-permutable semigroup is also (1,k)-commutative. In this paper this problem is solved for anyn less than or equal to eight and also whenn is any odd integer. For doing this we establish that if a semigroup satisfies a permutation identity of ordern then inevitably it also satisfies some permutation identities of ordern+1.     

Extremal problems on set systems

For a family $\boldmath{F}(k) = \{{\mathcal F}_1^{(k)}, {\mathcal F}_2^{(k)},\ldots,{\mathcal F}_t^{(k)}\}$ of k‐uniform hypergraphs let ex (n, F (k)) denote the maximum number of k‐tuples which a k‐uniform hypergraph on n vertices may have, while not containing any member of F (k). Let r_k(n) denote the maximum cardinality of a set of integers Z?[n], where Z contains no arithmetic progression of length k. For any k≥3 we introduce families $\boldmath{F}(k) = \{{\mathcal F}_1^{(k)},{\mathcal F}_2^{(k)}\}$ and prove that n^k?2r_k(n)≤ex (n_k², F (k))≤c_kn^k?1 holds. We conjecture that ex(n, F (k))=o(n^k?1) holds. If true, this would imply a celebrated result of Szemerédi stating that r_k(n)=o(n). By an earlier result o Ruzsa and Szemerédi, our conjecture is known to be true for k=3. The main objective of this article is to verify the conjecture for k=4. We also consider some related problems. © 2002 Wiley Periodicals, Inc. Random Struct. Alg. 20: 131–164, 2002.     

On extractors and exposure‐resilient functions for sublogarithmic entropy

We study resilient functions and exposure‐resilient functions in the low‐entropy regime. A resilient function (a.k.a. deterministic extractor for oblivious bit‐fixing sources) maps any distribution on n ‐bit strings in which k bits are uniformly random and the rest are fixed into an output distribution that is close to uniform. With exposure‐resilient functions, all the input bits are random, but we ask that the output be close to uniform conditioned on any subset of n ‐ k input bits. In this paper, we focus on the case that k is sublogarithmic in n. We simplify and improve an explicit construction of resilient functions for k sublogarithmic in n due to Kamp and Zuckerman (SICOMP 2006), achieving error exponentially small in k rather than polynomially small in k. Our main result is that when k is sublogarithmic in n, the short output length of this construction (O(log k) output bits) is optimal for extractors computable by a large class of space‐bounded streaming algorithms. Next, we show that a random function is a resilient function with high probability if and only if k is superlogarithmic in n, suggesting that our main result may apply more generally. In contrast, we show that a random function is a static (resp. adaptive) exposure‐resilient function with high probability even if k is as small as a constant (resp. loglog n). No explicit exposure‐resilient functions achieving these parameters are known. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

On the rainbow matching conjecture for 3-uniform hypergraphs

Aharoni and Howard and, independently, Huang et al. (2012) proposed the following rainbow version of the Erdős matching conjecture: For positive integers n, k and m with n ⩾ km, if each of the families \(F_{1},\ldots,F_{m}\subseteq\left(\begin{array}{c}[n]\\ k\end{array}\right)\) has size more than \(\max\{\left(\begin{array}{c}n\\ k\end{array}\right)-\left(\begin{array}{c}n-m+1\\ k\end{array}\right),\left(\begin{array}{c}km-1\\ k\end{array}\right)\}\), then there exist pairwise disjoint subsets e₁,…,e_m such that e_i ∈ F_i for all i ∈ [m]. We prove that there exists an absolute constant n₀ such that this rainbow version holds for k = 3 and n ⩾ n₀. We convert this rainbow matching problem to a matching problem on a special hypergraph H. We then combine several existing techniques on matchings in uniform hypergraphs: Find an absorbing matching M in H; use a randomization process of Alon et al. (2012) to find an almost regular subgraph of H − V(M); find an almost perfect matching in H − V(M). To complete the process, we also need to prove a new result on matchings in 3-uniform hypergraphs, which can be viewed as a stability version of a result of Łuczak and Mieczkowska (2014) and might be of independent interest.