Search

International audience; We introduce affine Volterra processes, defined as solutions of certain stochastic convolution equations with affine coefficients. Classical affine diffusions constitute a special case, but affine Volterra processes are neither semimartingales, nor Markov processes in general. We provide explicit exponential-affine representations of the Fourier--Laplace functional in terms of the solution of an associated system of deterministic integral equations, extending well-known formulas for classical affine diffusions. For specific state spaces, we prove existence, uniqueness, and invariance properties of solutions of the corresponding stochastic convolution equations. Our arguments avoid infinite-dimensional stochastic analysis as well as stochastic integration with respect to non-semimartingales, relying instead on tools from the theory of finite-dimensional deterministic convolution equations. Our findings generalize and simplify recent results in the literature on rough volatility models in finance.

Web crawling, snowball sampling, and respondent-driven sampling (RDS) are three types of network sampling techniques used to contact individuals in hard-to-reach populations. This paper studies these procedures as a Markov process on the social network that is indexed by a tree. Each node in this tree corresponds to an observation and each edge in the tree corresponds to a referral. Indexing with a tree (instead of a chain) allows for the sampled units to refer multiple future units into the sample. ¶ In survey sampling, the design effect characterizes the additional variance induced by a novel sampling strategy. If the design effect is some value $\operatorname{DE}$, then constructing an estimator from the novel design makes the variance of the estimator $\operatorname{DE}$ times greater than it would be under a simple random sample with the same sample size $n$. Under certain assumptions on the referral tree, the design effect of network sampling has a critical threshold that is a function of the referral rate $m$ and the clustering structure in the social network, represented by the second eigenvalue of the Markov transition matrix, $\lambda_{2}$. If $m1/\lambda_{2}^{2}$, then the design effect grows with $n$ (i.e., the standard estimator is no longer $\sqrt{n}$-consistent). Past this critical threshold, the standard error of the estimator converges at the slower rate of $n^{\log_{m}\lambda_{2}}$. The Markov model allows for nodes to be resampled; computational results show that the findings hold in without-replacement sampling. To estimate confidence intervals that adapt to the correct level of uncertainty, a novel resampling procedure is proposed. Computational experiments compare this procedure to previous techniques.

We introduce a Markov chain for sampling from the uniform distribution on a Riemannian manifold $\mathcal{M}$, which we call the $\textit{geodesic walk}$. We prove that the mixing time of this walk on any manifold with positive sectional curvature $C_{x}(u,v)$ bounded both above and below by $0 < \mathfrak{m}_{2} \leq C_{x}(u,v) \leq \mathfrak{M}_2 < \infty$ is $\mathcal{O}^*\left(\frac{\mathfrak{M}_2}{\mathfrak{m}_2}\right)$. In particular, this bound on the mixing time does not depend explicitly on the dimension of the manifold. In the special case that $\mathcal{M}$ is the boundary of a convex body, we give an explicit and computationally tractable algorithm for approximating the exact geodesic walk. As a consequence, we obtain an algorithm for sampling uniformly from the surface of a convex body that has running time bounded solely in terms of the curvature of the body., To appear in the Annals of Applied Probability

Determining the total variation mixing time of Kac’s random walk on the special orthogonal group $\mathrm{SO}(n)$ has been a long-standing open problem. In this paper, we construct a novel non-Markovian coupling for bounding this mixing time. The analysis of our coupling entails controlling the smallest singular value of a certain random matrix with highly dependent entries. The dependence of the entries in our matrix makes it not amenable to existing techniques in random matrix theory. To circumvent this difficulty, we extend some recent bounds on the smallest singular values of matrices with independent entries to our setting. These bounds imply that the mixing time of Kac’s walk on the group $\mathrm{SO}(n)$ is between $C_{1}n^{2}$ and $C_{2}n^{4}\log(n)$ for some explicit constants $0

We study a kinetically constrained Ising process (KCIP) associated with a graph $G$ and density parameter $p$; this process is an interacting particle system with state space $\{0,1\}^{G}$, the location of the particles. The number of particles at stationarity follows the $\operatorname{Binomial}(|G|,p$) distribution, conditioned on having at least one particle. The “constraint” in the name of the process refers to the rule that a vertex cannot change its state unless it has at least one neighbour in state “1”. The KCIP has been proposed by statistical physicists as a model for the glass transition, and more recently as a simple algorithm for data storage in computer networks. In this note, we study the mixing time of this process on the torus $G=\mathbb{Z}_{L}^{d}$, $d\geq3$, in the low-density regime $p=\frac{c}{|G|}$ for arbitrary $0

Determining the mixing time of Kac’s random walk on the sphere $\mathrm{S}^{n-1}$ is a long-standing open problem. We show that the total variation mixing time of Kac’s walk on $\mathrm{S}^{n-1}$ is between $\frac{1}{2}n\log(n)$ and $200n\log(n)$ for all $n$ sufficiently large. Our bound is thus optimal up to a constant factor, improving on the best-known upper bound of $O(n^{5}\log(n)^{2})$ due to Jiang [Ann. Appl. Probab. 22 (2012) 1712–1727]. Our main tool is a “non-Markovian” coupling recently introduced by the second author in [Ann. Appl. Probab. 24 (2014) 114–130] for obtaining the convergence rates of certain high dimensional Gibbs samplers in continuous state spaces.

The envelope model is a new paradigm to address estimation and prediction in multivariate analysis. Using sufficient dimension reduction techniques, it has the potential to achieve substantial efficiency gains compared to standard models. This model was first introduced by [Statist. Sinica 20 (2010) 927–960] for multivariate linear regression, and has since been adapted to many other contexts. However, a Bayesian approach for analyzing envelope models has not yet been investigated in the literature. In this paper, we develop a comprehensive Bayesian framework for estimation and model selection in envelope models in the context of multivariate linear regression. Our framework has the following attractive features. First, we use the matrix Bingham distribution to construct a prior on the orthogonal basis matrix of the envelope subspace. This prior respects the manifold structure of the envelope model, and can directly incorporate prior information about the envelope subspace through the specification of hyperparamaters. This feature has potential applications in the broader Bayesian sufficient dimension reduction area. Second, sampling from the resulting posterior distribution can be achieved by using a block Gibbs sampler with standard associated conditionals. This in turn facilitates computationally efficient estimation and model selection. Third, unlike the current frequentist approach, our approach can accommodate situations where the sample size is smaller than the number of responses. Lastly, the Bayesian approach inherently offers comprehensive uncertainty characterization through the posterior distribution. We illustrate the utility of our approach on simulated and real datasets.

In probability theory, equalities are much less than inequalities. In this paper, we find a series of equalities which characterize the symmetry of the forming times of a family of similar cycles for discrete-time and continuous-time Markov chains. Moreover, we use these cycle symmetries to study the circulation fluctuations for Markov chains. We prove that the empirical circulations of a family of cycles passing through a common state satisfy a large deviation principle with a rate function which has an highly non-obvious symmetry. Finally, we discuss the applications of our work in statistical physics and biochemistry., 30 pages, 1 figure

We characterize non-decreasing weight functions for which the associated one-dimensional vertex reinforced random walk (VRRW) localizes on 4 sites. A phase transition appears for weights of order $n\log \log n$: for weights growing faster than this rate, the VRRW localizes almost surely on at most 4 sites whereas for weights growing slower, the VRRW cannot localize on less than 5 sites. When $w$ is of order $n\log \log n$, the VRRW localizes almost surely on either 4 or 5 sites, both events happening with positive probability., Minor modifications

The Metropolis-adjusted Langevin (MALA) algorithm is a sampling algorithm which makes local moves by incorporating information about the gradient of the logarithm of the target density. In this paper we study the efficiency of MALA on a natural class of target measures supported on an infinite dimensional Hilbert space. These natural measures have density with respect to a Gaussian random field measure and arise in many applications such as Bayesian nonparametric statistics and the theory of conditioned diffusions. We prove that, started in stationarity, a suitably interpolated and scaled version of the Markov chain corresponding to MALA converges to an infinite dimensional diffusion process. Our results imply that, in stationarity, the MALA algorithm applied to an N-dimensional approximation of the target will take $\mathcal{O}(N^{1/3})$ steps to explore the invariant measure, comparing favorably with the Random Walk Metropolis which was recently shown to require $\mathcal{O}(N)$ steps when applied to the same class of problems., Comment: Published in at http://dx.doi.org/10.1214/11-AAP828 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

We show that certain Markov jump processes associated to crystal growth models are positive recurrent when the parameters satisfy a rather natural condition., Comment: Published at http://dx.doi.org/10.1214/105051606000000079 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

In this paper we study the problem of learning phylogenies and hidden Markov models. We call a Markov model nonsingular if all transition matrices have determinants bounded away from 0 (and 1). We highlight the role of the nonsingularity condition for the learning problem. Learning hidden Markov models without the nonsingularity condition is at least as hard as learning parity with noise, a well-known learning problem conjectured to be computationally hard. On the other hand, we give a polynomial-time algorithm for learning nonsingular phylogenies and hidden Markov models., Published at http://dx.doi.org/10.1214/105051606000000024 in the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

A Blackwell $\epsilon$-optimal strategy in a Markov Decision Process is a strategy that is $\epsilon$-optimal for every discount factor sufficiently close to 1. ¶ We prove the existence of Blackwell $\epsilon$-optimal strategies in finite Markov Decision Processes with partial observation.

This is the fourth in a series of papers devoted to the study of the large deviations of a Wright –Fisher process modeling the genetic evolution of a reproducing population.Variational considerations imply that if the process undergoes a large deviation, then it necessarily follows closely a definite path from its original to its current state. The favored paths were determined previously for a one-dimensional process subject to one-way mutation or natural selection, respectively, acting on a faster time scale than random genetic drift. The present paper deals with a general $d$-dimensional Wright–Fisher process in which any mutation or selection forces act on a time scale no faster than that of genetic drift. If the states of the process are represented as points on a $d$-sphere, then it can be shown that the position of a subcritically scaled process at a fixed “time” $T$ satisfies a large-deviation principle with rate function proportional to the square of the length of the great circle arc joining this position with the initial one (Hellinger–Bhattacharya distance). If a large deviation does occur, then the process follows with near certainty this arc at constant speed. The main technical problem circumvented is the degeneracy of the covariance matrix of the process at the boundary of the state space.

A stochastic process called vertex-reinforced random walk (VRRW) is defined in Pemantle [Ann. Probab. 16 1229-1241]. We consider this process in the case where the underlying graph is an infinite chain (i.e., process in the case where the underlying graph is an infinite chain (i.e., the one-dimensional integer lattice). We show that the range is almost surely finite, that at least five points are visited infinitely often almost surely and that with positive probability the range contains exactly five points. There are always points visited infinitely often but at a set of times of zero density, and we show that the number of visits to such a point to time n may be asymptotically n α for a dense set of values α ∈ (0, 1). The power law analysis relies on analysis of a related urn model.

This paper presents convergence conditions for a Markov chain constructed using Gibbs sampling, when the equilibrium distribution is the conditional sampling distribution of sufficient statistics from a generalized linear model. For cases when this unidimensional sampling is done approximately rather than exactly, the difference between the target equilibrium distribution and the resulting equilibrium distribution is expressed in terms of the difference between the true and approximating univariate conditional distributions. These methods are applied to an algorithm facilitating approximate conditional inference in canonical exponential families.

The present paper continues the work of two previous papers on the variational behavior, over a large number of generations, of a Wright-Fisher process modelling an even larger reproducing population. It was shown that a Wright-Fisher process subject to random drift and one-way mutation which undergoes a large deviation follows with near certainty a path which can be a trigonometric, exponential, hyperbolic or parabolic function. Here it is shown that a process subject to random drift and gamete selection follows in similar circumstances a path which is, apart from critical cases, a Jacobian elliptic function.

This paper is concerned with Markov chain models for flows of a finite population among a set of groups, where the individuals base their decisions on which group to go next partially on the current frequency distribution (profile). For a certain class of these models, the transition matrix of the profile process is analyzed algebraically, leading to surprisingly simple asymptotic results. Furthermore, in a model with after effects, the absorption probabilities are derived.

The competitive learning vector quantization (CLVQ) algorithm with constant step $\varepsilon > 0$--also known as the Kohonen algorithm with 0 neighbors--is studied when the stimuli are i.i.d. vectors. Its first noticeable feature is that, unlike the one-dimensional case which has $n!$ absorbing subsets, the CLVQ algorithm is "irreducible on open sets" whenever the stimuli distribution has a path-connected support with a nonempty interior. Then the Doeblin recurrence (or uniform ergodicity) of the algorithm is established under some convexity assumption on the support. Several properties of the invariant probability measure $\nu^{\varepsilon}$ are studied, including support location and absolute continuity with respect to the Lebesgue measure. Finally, the weak limit set of $\nu^{\varepsilon}$ as $\varepsilon \to 0$ is investigated.

An explanation of a remarkable identity in law, due to A. Dassios, concerning the $\alpha$-quantile of Brownian motion with drift is given with the help of Bertoin's rearrangement of positive and negative excursions for Brownian motion with drift.

We consider solid-on-solid models of two- and three-dimensional crystal growth described by Markov rate processes whose states are representations of the entire crystal surface and whose transitions are captures of single atoms by this surface or escapes of atoms. Under natural conditions on the transition probability rates, we prove ergodicity of the Markov process. This implies the existence of states of steady growth and statistically stationary surface structure. Microscopic surface instabilities do not therefore occur under such conditions. For two dimensions, our conditions are very general; for three dimensions, they are less general.

The stepping stone model describes a situation in which beasts alternately migrate among an infinite array of colonies, undergo random mating within each colony, and are subject to selectively neutral mutation at the rate $u$. Assume the beasts follow a random walk $\{X_n\}$. If $u = 0$, we show that two randomly chosen beasts in the $n$th generation in any bounded set are genetically identical at a given locus with probability converging to one iff the symmetrization of $\{X_n\}$ is recurrent. In general, if either $u = 0$ or $u$ is of order $1/n$, this probability converges to its limit at the rate $C/n^{\frac{1}{2}}$ for finite variance walks in one dimension and $C/(\log n)^a$ in two, with other rates for other classes of $\{X_n\}$. More complicated rates ensure for $u \neq O(1/n)$.

We show that there always exists a sequence of normalizing constants for the supercritical multitype Galton-Watson process so that the normalized sequence converges in probability to a limit which is proper and not identically zero. The Laplace-Stieltjes transform of the limit random variable is characterized as the unique solution under certain conditions of a vector Poincare functional equation.

We propose a control problem in which we minimize the expected hitting time of a fixed state in an arbitrary Markov chains with countable state space. A Markovian optimal strategy exists in all cases, and the value of this strategy is the unique solution of a nonlinear equation involving the transition function of the Markov chain.

We consider countable state, finite action dynamic programming problems with bounded rewards. Under Blackwell's optimality criterion, a policy is optimal if it maximizes the expected discounted total return for all values of the discount factor sufficiently close to 1. We give an example where a policy meets that optimality criterion, but is not optimal with respect to Derman's average cost criterion. We also give conditions under which this pathology cannot occur.