Discretized likelihood methods—asymptotic properties of discretized likelihood estimators (DLE's)

Suppose thatX ₁,X ₂, ...,X _n , ... is a sequence of i.i.d. random variables with a densityf(x, θ). Letc _n be a maximum order of consistency. We consider a solution \(\hat \theta _n \) of the discretized likelihood equation $$\sum\limits_{i = 1}^n {\log f(X_i ,\hat \theta _n + rc_n^{ - 1} ) - } \sum\limits_{i = 1}^n {\log f(X_i ,\hat \theta _n ) = a_n (\hat \theta _n ,r)} $$ wherea _n (θ,r) is chosen so that \(\hat \theta _n \) is asymptotically median unbiased (AMU). Then the solution \(\hat \theta _n \) is called a discretized likelihood estimator (DLE). In this paper it is shown in comparison with DLE that a maximum likelihood estimator (MLE) is second order asymptotically efficient but not third order asymptotically efficient in the regular case. Further it is seen that the asymptotic efficiency (including higher order cases) may be systematically discussed by the discretized likelihood methods.     

Estimation in the nonlinear errors-in-variables model

In the nonlinear structural errors-in-variables model we propose a consistent estimator of the unknown parameter, using a modified least squares criterion. Its rate of convergence strongly related to the regularity of the regression function, is generally slower than the parametric rate of convergence n^−1/2. Nevertheless, it is of order (log n)r/√n, r > 0, for some analytic regression functions.     

Evolutionary trees and the Ising model on the Bethe lattice: a proof of Steel��s conjecture

A major task of evolutionary biology is the reconstruction of phylogenetic trees from molecular data. The evolutionary model is given by a Markov chain on a tree. Given samples from the leaves of the Markov chain, the goal is to reconstruct the leaf-labelled tree. It is well known that in order to reconstruct a tree on n leaves, sample sequences of length ??(log n) are needed. It was conjectured by Steel that for the CFN/Ising evolutionary model, if the mutation probability on all edges of the tree is less than ${p^{\ast} = (\sqrt{2}-1)/2^{3/2}}$ , then the tree can be recovered from sequences of length O(log n). The value p* is given by the transition point for the extremality of the free Gibbs measure for the Ising model on the binary tree. Steel??s conjecture was proven by the second author in the special case where the tree is ??balanced.?? The second author also proved that if all edges have mutation probability larger than p* then the length needed is n ^??(1). Here we show that Steel??s conjecture holds true for general trees by giving a reconstruction algorithm that recovers the tree from O(log n)-length sequences when the mutation probabilities are discretized and less than p*. Our proof and results demonstrate that extremality of the free Gibbs measure on the infinite binary tree, which has been studied before in probability, statistical physics and computer science, determines how distinguishable are Gibbs measures on finite binary trees.     

Thermodynamics and statistical analysis of Gaussian random fields

Summary Gaussian fields are considered as Gibbsian fields. Thermodynamic functions are calculated for them and the variational principle is proved. As an application we get an approximation of log likelihood and an information theoretic interpretation of the asymptotic behaviour of the maximum likelihood estimator for Gaussian Markov fields.     

On likelihood estimation for a discretely observed jump process

We consider the parameter estimation problem for a Markov jump process sampled at periodic epochs with a constant step. Unlike the diffusion case where a closed form of the likelihood function is usually unavailable, we provide here an explicit expression of the likelihood function of the sampled chain. Moreover under suitable ergodicity condition on the jump process, we establish the consistency and the asymptotic normality of the likelihood estimator as the observation period tends to infinity. To cite this article: D. Dehay, J.-f. Yao, C. R. Acad. Sci. Paris, Ser. I 342 (2006).     

Combining empirical likelihood and generalized method of moments estimators: Asymptotics and higher order bias

This paper proposes an estimator combining empirical likelihood (EL) and the generalized method of moments (GMM) by allowing the sample average moment vector to deviate from zero and the sample weights to deviate from n⁻¹. The new estimator may be adjusted through free parameter δ∈(0,1) with GMM behavior attained as δ?0 and EL as δ?1. When the sample size is small and the number of moment conditions is large, the parameter space under which the EL estimator is defined may be restricted at or near the population parameter value. The support of the parameter space for the new estimator may be adjusted through δ. The new estimator performs well in Monte Carlo simulations.     

New Techniques for the Computation of Linear Recurrence Coefficients

The n coefficients of a fixed linear recurrence can be expressed through its m≤2n terms or, equivalently, the coefficients of a polynomial of a degree n can be expressed via the power sums of its zeros—by means of a polynomial equation known as the key equation for decoding the BCH error-correcting codes. The same problem arises in sparse multivariate polynomial interpolation and in various fundamental computations with sparse matrices in finite fields. Berlekamp's algorithm of 1968 solves the key equation by using order of n² operations in a fixed field. Several algorithms of 1975–1980 rely on the extended Euclidean algorithm and computing Padé approximation, which yields a solution in O(n(log n)² log log n) operations, though a considerable overhead constant is hidden in the “O” notation. We show algorithms (depending on the characteristic c of the ground field of the allowed constants) that simplify the solution and lead to further improvements of the latter bound, by factors ranging from order of log n, for c=0 and c>n (in which case the overhead constant drops dramatically), to order of min (c, log n), for 2≤c≤n; the algorithms use Las Vegas type randomization in the case of 2<c≤n.     

On systematic scan for sampling H‐colorings of the path

We show that systematic scan for H‐colorings of the n‐vertex path mixes in O(log n) scans for any fixed H using block dynamics. For a restricted family of H we furthermore show that systematic scan mixes in O(log n) scans for any scan order. For completeness we show that a random update Markov chain mixes in O(nlog n) updates for any fixed H. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Glauber dynamics for the mean-field Ising model: cut-off, critical power law, and metastability

We study the Glauber dynamics for the Ising model on the complete graph, also known as the Curie–Weiss Model. For β < 1, we prove that the dynamics exhibits a cut-off: the distance to stationarity drops from near 1 to near 0 in a window of order n centered at [2(1 ? β)]^?1 n log n. For β = 1, we prove that the mixing time is of order n ^3/2. For β > 1, we study metastability. In particular, we show that the Glauber dynamics restricted to states of non-negative magnetization has mixing time O(n log n).     

An Inversion-Free Estimating Equations Approach for Gaussian Process Models

One of the scalability bottlenecks for the large-scale usage of Gaussian processes is the computation of the maximum likelihood estimates of the parameters of the covariance matrix. The classical approach requires a Cholesky factorization of the dense covariance matrix for each optimization iteration. In this work, we present an estimating equations approach for the parameters of zero-mean Gaussian processes. The distinguishing feature of this approach is that no linear system needs to be solved with the covariance matrix. Our approach requires solving an optimization problem for which the main computational expense for the calculation of its objective and gradient is the evaluation of traces of products of the covariance matrix with itself and with its derivatives. For many problems, this is an O(nlog?n) effort, and it is always no larger than O(n²). We prove that when the covariance matrix has a bounded condition number, our approach has the same convergence rate as does maximum likelihood in that the Godambe information matrix of the resulting estimator is at least as large as a fixed fraction of the Fisher information matrix. We demonstrate the effectiveness of the proposed approach on two synthetic examples, one of which involves more than 1 million data points.     

Asymptotic Palm likelihood theory for stationary point processes

In the present paper, we propose a Palm likelihood approach as a general estimating principle for stationary point processes in $\mathbf{R}^d$ for which the density of the second-order factorial moment measure is available in closed form or in an integral representation. Examples of such point processes include the Neyman–Scott processes and the log Gaussian Cox processes. The computations involved in determining the Palm likelihood estimator are simple. Conditions are provided under which the Palm likelihood estimator is strongly consistent and asymptotically normally distributed.     

An O(n log m) algorithm for the Josephus Problem

The Josephus Problem can be described as follows: There are n objects arranged in a circle. Beginning with the first object, we move around the circle and remove every m th object. As each object is removed, the circle closes in. Eventually, all n objects will have been removed from the circle. The order in which the objects are removed induces a permutation on the integers 1 through n. Knuth has described two O(n log n) algorithms for generating this permuation. The problem of determining a more efficient algorithm for generating the permutation is left open. In this paper we give an O(n log m) algorithm.     

The extent of the maximum likelihood estimator for the extreme value index

In extreme value analysis, staring from Smith (1987) [1], the maximum likelihood procedure is applied in estimating the shape parameter of tails—the extreme value index γ. For its theoretical properties, Zhou (2009) [12] proved that the maximum likelihood estimator eventually exists and is consistent for γ>−1 under the first order condition. The combination of Zhou (2009) [12] and Drees et al (2004) [11] provides the asymptotic normality under the second order condition for γ>−1/2. This paper proves the asymptotic normality for −1<γ≤−1/2 and the non-consistency for γ<−1. These results close the discussion on the theoretical properties of the maximum likelihood estimator.     

On the complexity of calculating factorials

It is shown that n! can be evaluated with time complexity O(log log nM (n log n)), where M(n) is the complexity of multiplying two n-digit numbers together. This is effected, in part, by writing n! in terms of its prime factors. In conjunction with a fast multiplication this yields an O(n(log n log log n)²) complexity algorithm for n!. This might be compared to computing n! by multiplying 1 times 2 times 3, etc., which is ω(n² log n) and also to computing n! by binary splitting which is O(log nM(n log n)).     

On the set of natural numbers which only yield orders of Abelian groups

Let A denote the set of all natural numbers n such that every group of order n is Abelian. Let C denote the set of all natural numbers n such that every group of order n is cyclic. We prove that Σ_{n ≤ x,n?A?C}1 has roughly the order of magnitude x(log log x)^?1.     

Existence and consistency of the maximum likelihood estimator for the extreme value index

The paper is about the asymptotic properties of the maximum likelihood estimator for the extreme value index. Under the second order condition, Drees et al. [H. Drees, A. Ferreira, L. de Haan, On maximum likelihood estimation of the extreme value index, Ann. Appl. Probab. 14 (2004) 1179-1201] proved asymptotic normality for any solution of the likelihood equations (with shape parameter γ>−1/2) that is not too far off the real value. But they did not prove that there is a solution of the equations satisfying the restrictions.In this paper, the existence is proved, even for γ>−1. The proof just uses the domain of attraction condition (first order condition), not the second order condition. It is also proved that the estimator is consistent. When the second order condition is valid, following the current proof, the existence of a solution satisfying the restrictions in the above-cited reference is a direct consequence.     

Minimum f-divergence estimators and quasi-likelihood functions

Maximum quasi-likelihood estimators have several nice asymptotic properties. We show that, in many situations, a family of estimators, called the minimum f-divergence estimators, can be defined such that each estimator has the same asymptotic properties as the maximum quasi-likelihood estimator. The family of minimum f-divergence estimators include the maximum quasi-likelihood estimators as a special case. When a quasi-likelihood is the log likelihood from some exponential family, Amari's dual geometries can be used to study the maximum likelihood estimator. A dual geometric structure can also be defined for more general quasi-likelihood functions as well as for the larger family of minimum f-divergence estimators. The relationship between the f-divergence and the quasi-likelihood function and the relationship between the f-divergence and the power divergence is discussed.This work was supported by National Science Foundation grant DMS 88-03584.     

On the number of distinct block sizes in partitions of a set

The average number of distinct block sizes in a partition of a set of n elements is asymptotic to e log n as n → ∞. In addition, almost all partitions have approximately e log n distinct block sizes. This is in striking contrast to the fact that the average total number of blocks in a partition is ～n(log n)^?1 as n → ∞.     

Full likelihood inferences in the Cox model: an empirical likelihood approach

For the regression parameter β ₀ in the Cox model, there have been several estimators constructed based on various types of approximated likelihood, but none of them has demonstrated small-sample advantage over Cox’s partial likelihood estimator. In this article, we derive the full likelihood function for (β ₀, F ₀), where F ₀ is the baseline distribution in the Cox model. Using the empirical likelihood parameterization, we explicitly profile out nuisance parameter F ₀ to obtain the full-profile likelihood function for β ₀ and the maximum likelihood estimator (MLE) for (β ₀, F ₀). The relation between the MLE and Cox’s partial likelihood estimator for β ₀ is made clear by showing that Taylor’s expansion gives Cox’s partial likelihood estimating function as the leading term of the full-profile likelihood estimating function. We show that the log full-likelihood ratio has an asymptotic chi-squared distribution, while the simulation studies indicate that for small or moderate sample sizes, the MLE performs favorably over Cox’s partial likelihood estimator. In a real dataset example, our full likelihood ratio test and Cox’s partial likelihood ratio test lead to statistically different conclusions.     

Estimating linear functionals of a sparse family of Poisson means

Assume that we observe a sample of size n composed of p-dimensional signals, each signal having independent entries drawn from a scaled Poisson distribution with an unknown intensity. We are interested in estimating the sum of the n unknown intensity vectors, under the assumption that most of them coincide with a given “background” signal. The number s of p-dimensional signals different from the background signal plays the role of sparsity and the goal is to leverage this sparsity assumption in order to improve the quality of estimation as compared to the naive estimator that computes the sum of the observed signals. We first introduce the group hard thresholding estimator and analyze its mean squared error measured by the squared Euclidean norm. We establish a nonasymptotic upper bound showing that the risk is at most of the order of \(\sigma ^2(sp+s^2\sqrt{p}\log ^{3/2}(np))\). We then establish lower bounds on the minimax risk over a properly defined class of collections of s-sparse signals. These lower bounds match with the upper bound, up to logarithmic terms, when the dimension p is fixed or of larger order than \(s^2\). In the case where the dimension p increases but remains of smaller order than \(s^2\), our results show a gap between the lower and the upper bounds, which can be up to order \(\sqrt{p}\).