Estimation robuste pour des lois à symétrie elliptique à matrice de covariance inconnue

Let X,V₁,…,V_n−1 be n random vectors in ℝ^p with joint density of the form ƒ((X - θ)′ Σ⁻¹(X - θ) + Σ_j=1ⁿ⁻¹ V_jⁱ Σ⁻¹V_j), where both θ and Σ are unknown. We consider the problem of estimating θ under the invariant loss (δ - θ)′ Σ⁻¹ (δ - θ) and propose estimators which dominate the usual estimator δ₀(X) = X simultaneously for the entire class of such distributions. The proof involves the development of expressions which are analogous to unbiased estimators of risk and which in fact reduce to unbiased estimators of risk in the Gaussian case. The method is applicable to the case where Σ is structured.     

A study of random Weyl trees

We study binary search trees constructed from Weyl sequences {nθ}, n≥1, where θ is an irrational and {·} denotes “mod 1.” We explore various properties of the structure of these trees, and relate them to the continued fraction expansion of θ. If H_n is the height of the tree with n nodes when θ is chosen at random and uniformly on [0, 1], then we show that in probability, H_n∼(12/π²)log n log log n. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 271–295, 1998     

On p-intersection representations

For a graph G = (V,E) and integer p, a p-intersection representation is a family F = {S_x: × E V} of subsets of a set S with the property that |S_u ∩ S_ν| ≥ p ∩ {u, ν} E E. It is conjectured in [1] that θ_p(G) ≤ θ (K_n/2,n/2) (1 + o(1)) holds for any graph with n vertices. This is known to be true for p = 1 by [4]. In [1], θ (K_n/2,n/2) ≥ (n² + (2p− 1n)n)/4p is proved for any n and p. Here, we show that this is asymptotically best possible. Further, we provide a bound on θp(G) for all graphs with bounded degree. In particular, we prove θp(G) ≤ O(n^1/p) for any graph Gwith the maximum degree bounded by a constant. Finally, we also investigate the value of θ_p for trees. Improving on an earlier result of M. Jacobson, A. Kézdy, and D. West, (The 2-intersection number of paths and bounded-degree trees, preprint), we show that θ₂(T) ≤ O(d√n) for any tree T with maximum-degree d and θ₂(T) ≤ O(n^3/4) for any tree on n vertices. We conjecture that our results can be further improved and that θ₂(T) ≤ O(d√n) as long as Δ(T) ≤ √n. If this conjecture is true, our method gives θ₂(T) ≤ O(n^3/4) for any tree T which would be the best possible. © 1996 John Wiley & Sons, Inc.     

The cores of random hypergraphs with a given degree sequence

We study random r‐uniform n vertex hypergraphs with fixed degree sequence d = (d₁…,d_n), maximum degree Δ = o(n^1/24) and total degree θn, where θ is bounded. We give the size, number of edges and degree sequence of the κ ≥ 2) up to a whp error of O(n^2/3 Δ^4/3 log n). In the case of graphs (r = 2) we give further structural details such as the number of tree components and, for the case of smooth degree sequences, the size of the mantle. We give various examples, such as the cores of r‐uniform hypergraphs with a near Poisson degree sequence, and an improved upper bound for the first linear dependence among the columns in the independent column model of random Boolean matrices. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 25, 2004     

The p-Regular Partition Function Modulo p

Let b_?(n) denote the number of ?-regular partitions of n, where ? is a positive power of a prime p. We study in this paper the behavior of b_?(n) modulo powers of p. In particular, we prove that for every positive integer j, b_?(n) lies in each residue class modulo p^j for infinitely many values of n.     

On tree census and the giant component in sparse random graphs

For each of the two models of a sparse random graph on n vertices, G(n, # of edges = cn/2) and G(n, Prob (edge) = c/n) define t_n(k) as the total number of tree components of size k (1 ≤ k ≤ n). the random sequence {[t_n(k) - nh(k)]n^?1/2} is shown to be Gaussian in the limit n →∞, with h(k) = k^k?2c^k?1e^?kc/k! and covariance function being dependent upon the model. This general result implies, in particular, that, for c> 1, the size of the giant component is asymptotically Gaussian, with mean nθ(c) and variance n(1 ? T)^?2(1 ? 2Tθ)θ(1 ? θ) for the first model and n(1 ? T)^?2θ(1 ? θ) for the second model. Here Te^?T = ce^?c, T<1, and θ = 1 ? T/c. A close technique allows us to prove that, for c < 1, the independence number of G(n, p = c/n) is asymptotically Gaussian with mean nc^?1(β + β²/2) and variance n[c^?1(β + β²/2) ?c^?2(c + 1)β²], where βe^β = c. It is also proven that almost surely the giant component consists of a giant two-connected core of size about n(1 ? T)β and a “mantle” of trees, and possibly few small unicyclic graphs, each sprouting from its own vertex of the core.     

Statistically Efficient Thinning of a Markov Chain Sampler

It is common to subsample Markov chain output to reduce the storage burden. Geyer shows that discarding k ? 1 out of every k observations will not improve statistical efficiency, as quantified through variance in a given computational budget. That observation is often taken to mean that thinning Markov chain Monte Carlo (MCMC) output cannot improve statistical efficiency. Here, we suppose that it costs one unit of time to advance a Markov chain and then θ > 0 units of time to compute a sampled quantity of interest. For a thinned process, that cost θ is incurred less often, so it can be advanced through more stages. Here, we provide examples to show that thinning will improve statistical efficiency if θ is large and the sample autocorrelations decay slowly enough. If the lag ? ? 1 autocorrelations of a scalar measurement satisfy ρ_? > ρ_{? + 1} > 0, then there is always a θ < ∞ at which thinning becomes more efficient for averages of that scalar. Many sample autocorrelation functions resemble first order AR(1) processes with ρ_? = ρ^|?| for some ? 1 < ρ < 1. For an AR(1) process, it is possible to compute the most efficient subsampling frequency k. The optimal k grows rapidly as ρ increases toward 1. The resulting efficiency gain depends primarily on θ, not ρ. Taking k = 1 (no thinning) is optimal when ρ ? 0. For ρ > 0, it is optimal if and only if θ ? (1 ? ρ)²/(2ρ). This efficiency gain never exceeds 1 + θ. This article also gives efficiency bounds for autocorrelations bounded between those of two AR(1) processes. Supplementary materials for this article are available online.     

Optimal binary covering codes of length 2j

The minimum size of a binary covering code of length n and covering radius r is denoted by K(n,r), and codes of this length are called optimal. For j > 0 and n = 2^j, it is known that K(n,1) = 2 · K(n?1,1) = 2^{n ? j}. Say that two binary words of length n form a duo if the Hamming distance between them is 1 or 2. In this paper, it is shown that each optimal binary covering code of length n = 2^j, j > 0, and covering radius 1 is the union of duos in just one way, and that the closed neighborhoods of the duos form a tiling of the set of binary words of length n. Methods of constructing such optimal codes from optimal covering codes of length n ? 1 (that is, perfect single‐error‐correcting codes) are discussed. The paper ends with the construction of an optimal covering code of length 16 that does not contain an extension of any optimal covering code of length 15. © 2005 Wiley Periodicals, Inc. J Combin Designs     

Multiparameter acoustic imaging in the born approximation

Samples of biological tissue are modelled as inhomogeneous fluids with density ?(X) and sound speed c(x) at point x. The samples are contained in the sphere |x| ? δ and it is assumed that ?(x) ? ?₀ = 1 and c(x) ? c₀ = 1 for |x| ? δ, and |γ_n(x)| ? 1 and |?γ?(x)| ? 1 where γ?(x) = ?(x) ? 1 and γ_n(x) = c^?2(x) ? 1. The samples are insonified by plane pulses s(x · θ₀ – t) where x = |θ₀| = 1 and the scattered pulse is shown to have the form |x|^?1 e_s(|x| – t, θ, θ₀) in the far field, where x = |x| θ. The response e_s(τ, θ, θ₀) is measurable. The goal of the work is to construct the sample parameters γn and γ? from e_s(τ, θ, θ₀) for suitable choiches of s, θ and θ₀. In the limiting case of constant density: γ?(x)_? 0 it is shown that Where δ represents the Dirac δ and S² is the unit sphere |θ| = 1. Analogous formulas, based on two sets of measurements, are derived for the case of variable c(x) and ?(x).     

Tractability of Multivariate Integration for Weighted Korobov Classes

We study the worst-case error of multivariate integration in weighted Korobov classes of periodic functions of d coordinates. This class is defined in terms of weights γ_j which moderate the behavior of functions with respect to successive coordinates. We study two classes of quadrature rules. They are quasi-Monte Carlo rules which use n function values and in which all quadrature weights are 1/n and rules for which all quadrature weights are non-negative. Tractability for these two classes of quadrature rules means that the minimal number of function values needed to guarantee error in the worst-case setting is bounded by a polynomial in d and ⁻¹. Strong tractability means that the bound does not depend on d and depends polynomially on ⁻¹. We prove that strong tractability holds iff ∑^∞_j=1 γ_j<∞, and tractability holds iff lim sup_d→∞ ∑^d_j=1 γ_j/log d<∞. Furthermore, strong tractability or tractability results are achieved by the relatively small class of lattice rules. We also prove that if ∑^∞_j=1 γ^1/α_j<∞, where α measures the decay of Fourier coefficients in the weighted Korobov class, then for d1, n prime and δ>0 there exist lattice rules that satisfy an error bound independent of d and of order n^−α/2+δ. This is almost the best possible result, since the order n^−α/2 cannot be improved upon even for d=1. A corresponding result is deduced for weighted non-periodic Sobolev spaces: if ∑^∞_j=1 γ^1/2_j<∞, then for d1, n prime and δ>0 there exist shifted lattice rules that satisfy an error bound independent of d and of order n^−1+δ. We also check how the randomized error of the (classical) Monte Carlo algorithm depends on d for weighted Korobov classes. It turns out that Monte Carlo is strongly tractable iff ∑^∞_j=1 log γ_j<∞ and tractable iff lim sup_d→∞ ∑^d_j=1 log γ_j/log d<∞. Hence, in particular, for γ_j=1 we have the usual Korobov space in which integration is intractable for the two classes of quadrature rules in the worst-case setting, whereas Monte Carlo is strongly tractable in the randomized setting.     

Relative probabilities of majority winners under partial information

Suppose the only observable characteristic of each of n random variables that is uniformly distributed on the six rankings of objects in a three-element set is its first-ranked object. Let ?(n₁,n₂,n₃) be the probability that one of the three objects has majorities over the other two within the rankings when n_j of the n rankings have the jth object in first place. It is assumed that n is odd, so that ?(n₁,n₂,n₃)=1 only if n_j≥(n+1)/2 for some j.It is shown that $\text{?(a+1,b,c)<?(a,b+1,c) if a <b,a ≤ c ≤ b+1}$ and max {b,c}≤(n?1)/2. It follows from this that ? is minimized for fixed n if and only if n_j?n_k≤1 for all j,k? {1,2,3}. However, ? does not necessarily increase when two of its arguments get farther apart. For example, ?(b,b,3)>?(b?1,b+1,3) for b≥28, and ?(b,b,2b?1)>?(b?1,b+1,2b?1) for b≥12.     

On the rational approximation ofe −x on [0, ∞)

In recent years the problem of uniform approximation ofe ^?x on [0, ∞) by rational functions has found wide interest. In this paper we present a method for the construction of rational approximations toe ^?x that seem to come arbitrarily near to the asymptotically best one. We start with a generalization of the integral form of the Padé approximant by introducing certain real parametersa _j ,b _i ,k and?. The corresponding error function has again an integral representation and is estimated for everyx∈[0,∞) by the Laplace method. This leads to the consideration of a finite number of new error functionsφ _i·j whose maxima are determined by a set of nonlinear equations and, under some restrictions on thea _j ,b _i ,k, and?, are also unique. Variation of these parameters according to a special algorithm and computation of the corresponding maxima of the functionsφ _i·j shows that forn→∞ the order of rational approximation ofe ^?x on [0, ∞) is at least 9.03^?n .     

Asymptotic normality of H-L estimators based on dependent data

LetX ₁,X ₂, ... be a strictly stationary φ-mixing sequence of r.v.'s with a common continuous cdfF. Let θ be a location parameter ofF. We prove the asymptotic normality of a class of Hodges-Lehmann estimators of θ under various regularity conditions on the mixing number φ and the underlyingF. We also establish the asymptotic linearity of signed rank statistics in the parameter θ. Our results also enable us to study the effect of φ-dependence on the asymptotic power of signed rank tests for testingH ₀: θ=0 againstH _n :θ=θ ₀ n ^?1/2,θ ₀≠0. Finally these results are shown to remain valid for strongly mixing processes {X _i } also.     

Real Zeros of Algebraic Polynomials with Dependent Random Coefficients

The expected number of real zeros of polynomials a ₀ + a ₁ x + a ₂ x ² +…+a _n?1 x ^n?1 with random coefficients is well studied. For n large and for the normal zero mean independent coefficients, irrespective of the distribution of coefficients, this expected number is known to be asymptotic to (2/π)log n. For the dependent cases studied so far it is shown that this asymptotic value remains O(log n). In this article, we show that when cov(a _i , a _j ) = 1 ? |i ? j|/n, for i = 0,…, n ? 1 and j = 0,…, n ? 1, the above expected number of real zeros reduces significantly to O(log n)^1/2.     

Boundedness of multilinear commutators of generalized fractional integrals

Let L be the infinitesimal generator of an analytic semigroup on L²(?ⁿ ) with Gaussian kernel bound, and let L^{–α /2} be the fractional integral of L for 0 < α < n. Suppose that b = (b₁, b₂, …, b_m ) is a finite family of locally integral functions, then the multilinear commutator generated by b and L^{–α /2} is defined by L^{–α /2} _b f = [b_m , …, [b₂, [b₁, L^{–α /2}]], …, ] f, where m ∈ ?⁺. When b₁, b₂, …, b_m ∈ BMO or b_j ∈ Λ (0 < β_j < 1) for 1 ≤ j ≤ m, the authors study the boundedness of L^{–α /2} _b . (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Bayesian estimation of the product of two proportions

Suppose that for i = 1,2, a Bernoulli random variable with success probability θ_i is observable from population i. The problem is to estimate θ = θ₁θ₂ using a Bayesian approach with squared error estimation loss in θ. For estimating θ, the best nonrandom sampling scheme, the two-stage sampling scheme, and the optimal sampling scheme are discussed. It is shown that the two-stage sampling scheme is typically asymptotically optimal, and can improve the Bayes risk (over the best nonrandom allocation) up to fifty percent     

The inverse M-matrix problem

One aspect of the inverse M-matrix problem can be posed as follows. Given a positive n × n matrix A=(a_ij) which has been scaled to have unit diagonal elements and off-diagonal elements which satisfy 0 < y ? a_ij ? x < 1, what additional element conditions will guarantee that the inverse of A exists and is an M-matrix? That is, if A^?1=B=(b_ij), then b_ii> 0 and b_ij ? 0 for i≠_j. If n=2 or x=y no further conditions are needed, but if n ? 3 and y < x, then the following is a tight sufficient condition. Define an interpolation parameter s via x²=sy+(1?s)y²; then B is an M-matrix if s^?1 ? n?2. Moreover, if all off-diagonal elements of A have the value y except for a_ij=a_jj=x when i=n?1, n and 1 ? _j ? n?2, then the condition on both necessary and sufficient for B to be an M-matrix.     

New tight frames of curvelets and optimal representations of objects with piecewise C2 singularities

This paper introduces new tight frames of curvelets to address the problem of finding optimally sparse representations of objects with discontinuities along piecewise C² edges. Conceptually, the curvelet transform is a multiscale pyramid with many directions and positions at each length scale, and needle‐shaped elements at fine scales. These elements have many useful geometric multiscale features that set them apart from classical multiscale representations such as wavelets. For instance, curvelets obey a parabolic scaling relation which says that at scale 2^?j, each element has an envelope that is aligned along a “ridge” of length 2^?j/2 and width 2^?j. We prove that curvelets provide an essentially optimal representation of typical objects f that are C² except for discontinuities along piecewise C² curves. Such representations are nearly as sparse as if f were not singular and turn out to be far more sparse than the wavelet decomposition of the object. For instance, the n‐term partial reconstruction f obtained by selecting the n largest terms in the curvelet series obeys This rate of convergence holds uniformly over a class of functions that are C² except for discontinuities along piecewise C² curves and is essentially optimal. In comparison, the squared error of n‐term wavelet approximations only converges as n^?1 as n → ∞, which is considerably worse than the optimal behavior. © 2003 Wiley Periodicals, Inc.     

The product of linear nonhomogeneous forms

We show that for an arbitrary unimodular lattice Λ of dimension n and an arbitrary point C =(c₁, c₂...c_n) ? Rⁿ a point Y = (y₁, y₂,..., y_n) ε Λ can be found and also a number h, satisfying the condition 1 ?h ? 2^?n/2 θ^?1 + 1 (0 < θ ? 2^?n/2), such that the inequality $$\prod\nolimits_{i = 1}^n {\left| {Y_i + hc_i } \right|}< \theta $$ will be satisfied.     

Reconstituting the distribution of the components of a random Vector from distributions of certain statistics

Let (X₁, ..., X_n) be a random vector with independent components. It is proven in this paper that, under certain restrictions, the distributions of the pairS ₁=sup (a ₁X₁, ..., a_nX_n) andS ₂=sup (b₁X₁,...,b_nX_n) univocally define the distribution function of the components X_j.Translated from Matematicheskie Zametki, Vol. 13, No. 6, pp. 889–892, June, 1973.