q-Bernstein polynomials and their iterates

Let B_n( f,q;x), n=1,2,… be q-Bernstein polynomials of a function f : [0,1]→C. The polynomials B_n( f,1;x) are classical Bernstein polynomials. For q≠1 the properties of q-Bernstein polynomials differ essentially from those in the classical case. This paper deals with approximating properties of q-Bernstein polynomials in the case q>1 with respect to both n and q. Some estimates on the rate of convergence are given. In particular, it is proved that for a function f analytic in {z: |z|<q+} the rate of convergence of {B_n( f,q;x)} to f(x) in the norm of C[0,1] has the order q⁻ⁿ (versus 1/n for the classical Bernstein polynomials). Also iterates of q-Bernstein polynomials {B_n^j_n( f,q;x)}, where both n→∞ and j_n→∞, are studied. It is shown that for q(0,1) the asymptotic behavior of such iterates is quite different from the classical case. In particular, the limit does not depend on the rate of j_n→∞.     

Testing of matrix-poset properties

Combinatorial property testing, initiated by Rubinfeld and Sudan [23] and formally defined by Goldreich, Goldwasser and Ron in [18], deals with the following relaxation of decision problems: Given a fixed property P and an input f, distinguish between the case that f satisfies P, and the case that no input that differs from f in less than some fixed fraction of the places satisfies P. An (ε, q)-test for P is a randomized algorithm that queries at most q places of an input f and distinguishes with probability 2/3 between the case that f has the property and the case that at least an ε-fraction of the places of f need to be changed in order for it to have the property. Here we concentrate on labeled, d-dimensional grids, where the grid is viewed as a partially ordered set (poset) in the standard way (i.e. as a product order of total orders). The main result here presents an (ε, poly(1/ε))-test for every property of 0/1 labeled, d-dimensional grids that is characterized by a finite collection of forbidden induced posets. Such properties include the “monotonicity” property studied in [9,8,13], other more complicated forbidden chain patterns, and general forbidden poset patterns. We also present a (less efficient) test for such properties of labeled grids with larger fixed size alphabets. All the above tests have in addition a 1-sided error probability. This class of properties is related to properties that are defined by certain first order formulae with no quantifier alternation over the syntax containing the grid order relations. We also show that with one quantifier alternation, a certain property can be defined, for which no test with query complexity of O(n ^1/4) (for a small enough fixed ε) exists. The above results identify new classes of properties that are defined by means of restricted logics, and that are efficiently testable. They also lay out a platform that bridges some previous results. A preliminary version of these results formed part of [14]. Research supported in part by grant 55/03 from the Israel Science Foundation.     

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     

Compound Binomial Approximations

We consider the approximation of the convolution product of not necessarily identical probability distributions q _j I + p _j F, (j=1,...,n), where, for all j, p _j =1−q _j ∈[0, 1], I is the Dirac measure at point zero, and F is a probability distribution on the real line. As an approximation, we use a compound binomial distribution, which is defined in a one-parametric way: the number of trials remains the same but the p _j are replaced with their mean or, more generally, with an arbitrary success probability p. We also consider approximations by finite signed measures derived from an expansion based on Krawtchouk polynomials. Bounds for the approximation error in different metrics are presented. If F is a symmetric distribution about zero or a suitably shifted distribution, the bounds have a better order than in the case of a general F. Asymptotic sharp bounds are given in the case, when F is symmetric and concentrated on two points. An erratum to this article can be found at     

Limiting distribution of sums of nonnegative stationary random variables

Summary Let {X _n,j,−∞<j<∞∼,n≧1, be a sequence of stationary sequences on some probability space, with nonnegative random variables. Under appropriate mixing conditions, it is shown thatS _n=X_n,1+…+X _n,n has a limiting distribution of a general infinitely divisible form. The result is applied to sequences of functions {f _n(x)∼ defined on a stationary sequence {X _j∼, whereX _n.f=f_n(X_j). The results are illustrated by applications to Gaussian processes, Markov processes and some autoregressive processes of a general type. This paper represents results obtained at the Courant Institute of Mathematical Sciences, New York University, under the sponsorship of the National Sciences Foundation, Grant MCS 82-01119.     

On the number of queries necessary to identify a permutation

Let p and q be two permutations over {1, 2,…, n}. We denote by m(p, q) the number of integers i, 1 ≤ i ≤ n, such that p(i) = q(i). For each fixed permutation p, a query is a permutation q of the same size and the answer a(q) to this query is m(p, q). We investigate the problem of finding the minimum number of queries required to identify an unknown permutation p. A polynomial-time algorithm that identifies a permutation of size n by O(n · log₂n) queries is presented. The lower bound of this problem is also considered. It is proved that the problem of determining the size of the search space created by a given set of queries and answers is #P-complete. Since this counting problem is essential for the analysis of the lower bound, a complete analysis of the lower bound appears infeasible. We conjecture, based on some preliminary analysis, that the lower bound is Ω(n · log₂n).     

The Length of the Longest Increasing Subsequence of a Random Mallows Permutation

The Mallows measure on the symmetric group S _n is the probability measure such that each permutation has probability proportional to q raised to the power of the number of inversions, where q is a positive parameter and the number of inversions of π is equal to the number of pairs i<j such that π _i >π _j . We prove a weak law of large numbers for the length of the longest increasing subsequence for Mallows distributed random permutations, in the limit that n→∞ and q→1 in such a way that n(1?q) has a limit in R.     

Fast formula of a reliability ofm-consecutive-k-out-of-n:F system with cyclek

Anm-consecutive-k-out-of-n:F system is a system ofn linearly arranged components which fails if and only if at leastm non-overlapping sequences ofk components fail, when there arek distinct components with failure probabilitiesq _i fori=1,...,k and where the failure probability of thej-th component (j=rk+i (1 ≤i ≤k) isq _j =q _i , we call this system by anm-consecutive-k-out-of-n:F system with cycle (or period)k. In this paper we give a formula of the failure probability ofm-consecutive-k-out-of-n:F system with cyclek via the failure probability of consecutive-k-out-of-n:F system.     

Points of {varepsilon} Differentiability of Lipschitz Functions from Rn to Rn-1

This paper proves that for every Lipschitz function f : RⁿR^m,m < n, there exists at least one point of -differentiabilityof f which is in the union of all m-dimensional affine subspacesof the form q0 +span{q1,q2,...,q_m}, where q_j (j = 0,1,...,m)are points in Rⁿ with rational coordinates. 2000 MathematicsSubject Classification 26B05, 26B35.     

Succinct data structures for flexible text retrieval systems

We propose succinct data structures for text retrieval systems supporting document listing queries and ranking queries based on the tf*idf (term frequency times inverse document frequency) scores of documents. Traditional data structures for these problems support queries only for some predetermined keywords. Recently Muthukrishnan proposed a data structure for document listing queries for arbitrary patterns at the cost of data structure size. For computing the tf*idf scores there has been no efficient data structures for arbitrary patterns.Our new data structures support these queries using small space. The space is only 2/ times the size of compressed documents plus 10n bits for a document collection of length n, for any 0<1. This is much smaller than the previous O(nlogn) bit data structures. Query time is O(m+qlogn) for listing and computing tf*idf scores for all q documents containing a given pattern of length m. Our data structures are flexible in a sense that they support queries for arbitrary patterns.     

The largest connected component in a random mapping

A random mapping (T; q) of a finite set V = {1, 2,…,n} into itself assigns independently to each i ? V its unique image j = TT(i)E V with probability q for i = j and with probability $ \frac{{1 - q}}{{n - 1}} $ for j ≠ i. The purpose of the article is to determine the asymptotic behaviour of the size of the largest connected component of the random digraph G_T(q) representing thes mapping as n–x, regarding all possible values of the parameter q = q(n). © 1994 John Wiley & Sons, Inc.     

The Distribution of Condition Numbers of Rational Data of Bounded Bit Length

We prove that rational data of bounded input length are uniformly distributed (in the classical sense of H. Weyl, in [42]) with respect to the probability distribution of condition numbers of numerical analysis. We deal both with condition numbers of linear algebra and with condition numbers for systems of multivariate polynomial equations. For instance, we prove that for a randomly chosen n\times n rational matrix M of bit length O(n ⁴ log n) + log w , the condition number k(M) satisfies k(M) ≤ w n ^5/2 with probability at least 1-2w ^-1 . Similar estimates are established for the condition number μ_ norm of M. Shub and S. Smale when applied to systems of multivariate homogeneous polynomial equations of bounded input length. Finally, we apply these techniques to estimate the probability distribution of the precision (number of bits of the denominator) required to write approximate zeros of systems of multivariate polynomial equations of bounded input length. March 7, 2001. Final version received: June 7, 2001.     

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     

Degree frequencies in digraphs and tournaments

The number of vertices in a digraph G having a particular outdegree (indegree) is called the frequency of the outdegree (indegree). A set F of distinct positive integers {f₁, f₂, …, f_n} is the frequency set of the digraph G if every outdegree and indegree occurs with frequency f_j∈F and for each f_j∈F there is a least one outdegree and at least one indegree with frequency f_j. We prove that each nonempty set F of positive integers is the frequency set of some tournament, and we determine the smallest possible order for such a tournament. Similar results for asymmetric digraphs are also given. The results and techniques for frequency sets are used to derive corresponding results for vertex frequency partitions.     

On the Convergence and Iterates of q-Bernstein Polynomials

The convergence properties of q-Bernstein polynomials are investigated. When q1 is fixed the generalized Bernstein polynomials _nf of f, a one parameter family of Bernstein polynomials, converge to f as n→∞ if f is a polynomial. It is proved that, if the parameter 0<q<1 is fixed, then _nf→f if and only if f is linear. The iterates of _nf are also considered. It is shown that _n^Mf converges to the linear interpolating polynomial for f at the endpoints of [0,1], for any fixed q>0, as the number of iterates M→∞. Moreover, the iterates of the Boolean sum of _nf converge to the interpolating polynomial for f at n+1 geometrically spaced nodes on [0,1].     

Extended abstract theory of universal series and applications

In this article, we extend the recently developed abstract theory of universal series to include averaged sums of the form \frac1f(n)?_j=0ⁿ a_j x_j{\frac{1}{\phi(n)}\sum_{j=0}^{n} a_j x_j} for a given fixed sequence of vectors (x _j ) in a topological vector space X over a field \mathbbK{\mathbb{K}} of real or complex scalars, where (f(n)){(\phi(n))} is a sequence of non-zero field scalars. We give necessary and sufficient conditions for the existence of a sequence of coefficients (a _j ) which make the above sequence of averaged sums dense in X. When applied, the extended theory gives new analogues to well known classical theorems including those of Seleznev, Fekete and Menchoff.     

A weak difference set construction for higher dimensional designs

We continue the analysis of de Launey's modification of development of designs modulo a finite groupH by the action of an abelian extension function (AEF), and of the proper higher dimensional designs which result.We extend the characterization of allAEFs from the cyclic group case to the case whereH is an arbitrary finite abelian group.We prove that ourn-dimensional designs have the form (f(j ₁ j ₂ ...j _n )) (j _i J), whereJ is a subset of cardinality |H| of an extension groupE ofH. We say these designs have a weak difference set construction.We show that two well-known constructions for orthogonal designs fit this development scheme and hence exhibit families of such Hadamard matrices, weighing matrices and orthogonal designs of orderv for which |E|=2v. In particular, we construct proper higher dimensional Hadamard matrices for all orders 4t100, and conference matrices of orderq+1 whereq is an odd prime power. We conjecture that such Hadamard matrices exist for all ordersv0 mod 4.     

Bounds for fixed point free elements in a transitive group and applications to curves over finite fields

We investigateV _f , the cardinality of the value set of a polynomialf of degreen over a finite field of cardinalityq. It has been shown that iff is not bijective, thenV _f ≤q−(q−1)/n. Polynomials do exist which essentially achieve that bound. We do prove that if the degree off is prime to the characteristic andf is not bijective, then asymptoticallyV _f ≤(5/6)q. We consider related problems for curves and higher dimensional varieties. This problem is related to the number of fixed point free elements in finite groups, and we prove some results in that setting as well. Both authors partially supported by the NSF.     

Matrices associated with arithmetical functions

Let f be an arithmetical function and S={x ₁,x ₂,…,x_n } a set of distinct positive integers. Denote by [f(x_i ,x_j }] the n×n matrix having f evaluated at the greatest common divisor (x_i ,x_j ) of x_i , and x_j as its i j-entry. We will determine conditions on f that will guarantee the matrix [f(x_i ,x_j )] is positive definite and, in fact, has properties similar to the greatest common divisor (GCD) matrix

[(x_i ,x_j )] where f is the identity function. The set S is gcd-closed if (x_i ,x_j )∈S for 1≤ i j ≤ n. If S is gcd-closed, we calculate the determinant and (if it is invertible) the inverse of the matrix [f(x_i ,x_j )]. Among the examples of determinants of this kind are H. J. S. Smith's determinant det[(i,j)].     

A note on certain functional determinants

Summary We consider the problem when a scalar function ofn variables can be represented in the form of a determinant det(f _i (x _j )), the so-called Casorati determinant off ₁,f ₂,,f _n . The result is applied to the solution of some functional equations with unknown functionsH of two variables that involve determinants det(H(x _i ,x _j )).