The hardcore model on a graph$G$with parameter$\lambda > 0$is a probability measure on the collection of all independent sets of$G$, that assigns to each independent set$I$a probability proportional to$\lambda ^{|I|}$. In this paper we consider the problem of estimating the parameter$\lambda $given a single sample from the hardcore model on a graph$G$. To bypass the computational intractability of the maximum likelihood method, we use the maximum pseudo-likelihood (MPL) estimator, which for the hardcore model has a surprisingly simple closed form expression. We show that for any sequence of graphs$\{G_{N}\}_{N \geq 1}$, where$G_{N}$is a graph on$N$vertices, the MPL estimate of$\lambda $is$\sqrt {N}$-consistent (that is, it converges to the true parameter at rate$1/\sqrt {N}$), whenever the graph sequence has uniformly bounded average degree. We then extend our methods to obtain estimates for the vector of activity parameters in general$H$-coloring models, in which restrictions between adjacent colors are encoded by a constraint graph$H$. These constitute an important class of Markov random fields that includes all hard-constraint models, which arise in a broad array of fields including combinatorics, statistical physics, and communication networks. Given a single sample from an$H$-coloring model, we derive sufficient conditions under which the MPL estimate is$\sqrt {N}$-consistent. Moreover, we verify the sufficient conditions for$H$-coloring models for which there is at least one ‘unconstrained’ color (that is, there exists at least one vertex in the constraint graph$H$that is connected to all vertices), as long as the graph sequence has uniformly bounded average degree. This applies to many$H$-coloring examples such as the Widom-Rowlinson and multi-state hard-core models. On the other hand, for the$q$-coloring model, which falls outside this class, we show that the condition can fail and consistent estimation may be impossible even for graphs with bounded average degree. Nevertheless, we show that the MPL estimate is$\sqrt {N}$-consistent in the$q$-coloring model when$\{G_{N}\}_{N \geq 1}$has bounded average double neighborhood. The presence of hard constraints, as opposed to soft constraints, leads to new challenges, and our proofs entail applications of the method of exchangeable pairs as well as combinatorial arguments that employ the probabilistic method.

The paper studies distributed static parameter (vector) estimation in sensor networks with nonlinear observation models and noisy intersensor communication. It introduces separably estimable observation models that generalize the observability condition in linear centralized estimation to nonlinear distributed estimation. It studies two distributed estimation algorithms in separably estimable models, theNU(with its linear counterpartLU) and theNLU. Their update rule combines a consensus step (where each sensor updates the state by weight averaging it with its neighbors' states) and an innovation step (where each sensor processes its local current observation). This makes the three algorithms of the consensus + innovations type, very different from traditional consensus. This paper proves consistency (all sensors reach consensus almost surely and converge to the true parameter value), efficiency, and asymptotic unbiasedness. ForLUandNU, it proves asymptotic normality and provides convergence rate guarantees. The three algorithms are characterized by appropriately chosen decaying weight sequences. AlgorithmsLUandNUare analyzed in the framework of stochastic approximation theory; algorithmNLUexhibits mixed time-scale behavior and biased perturbations, and its analysis requires a different approach that is developed in this paper.

The classical hard core model from statistical physics, with activity [Formula: see text] and capacity [Formula: see text], on a graph [Formula: see text], concerns a probability measure on the set [Formula: see text] of independent sets of [Formula: see text], with the measure of each independent set [Formula: see text] being proportional to [Formula: see text]. Ramanan et al. [K. Ramanan, A. Sengupta, I. Ziedins and P. Mitra, Adv. Appl. Probab., 34 (2002), pp. 1–27] proposed a generalization of the hard core model as an idealized model of multicasting in communication networks. In this generalization, the multistate hard core model, the capacity [Formula: see text] is allowed to be a positive integer, and a configuration in the model is an assignment of states from [Formula: see text] to [Formula: see text] (the set of nodes of [Formula: see text]) subject to the constraint that the states of adjacent nodes may not sum to more than [Formula: see text]. The activity associated to state [Formula: see text] is [Formula: see text], so that the probability of a configuration [Formula: see text] is proportional to [Formula: see text]. In this work, we consider this generalization when [Formula: see text] is an infinite rooted [Formula: see text]-ary tree and prove rigorously some of the conjectures made by Ramanan et al. In particular, we show that the [Formula: see text] model exhibits a (first-order) phase transition at a larger value of [Formula: see text] than the [Formula: see text] model exhibits its (second-order) phase transition. In addition, for large [Formula: see text] we identify a short interval of values for [Formula: see text] above which the model exhibits phase coexistence and below which there is phase uniqueness. For odd [Formula: see text], this transition occurs in the region of [Formula: see text], while for even [Formula: see text], it occurs around [Formula: see text]. In the latter case, the transition is first-order.

A key criterion in the design of high-speed networks is the probability that the buffer content exceeds a given threshold. We consider n independent identical traffic sources modelled as point processes, which are fed into a link with speed proportional to n. Under fairly general assumptions on the input processes we show that the steady state probability of the buffer content exceeding a threshold b>0 tends to the corresponding probability assuming Poisson input processes. We verify the assumptions for a large class of long-range dependent sources commonly used to model data traffic. Our results show that with superposition, significant multiplexing gains can be achieved for even smaller buffers than suggested by previous results, which consider O(n) buffer size. Moreover, simulations show that for realistic values of the exceedance probability and moderate utilisations, convergence to the Poisson limit takes place at reasonable values of the number of sources superposed. This is particularly relevant for high-speed networks in which the cost of high-speed memory is significant.