• ### Critical random forests(1709.07514)

July 2, 2018 math.PR
Let $F(N,m)$ denote a random forest on a set of $N$ vertices, chosen uniformly from all forests with $m$ edges. Let $F(N,p)$ denote the forest obtained by conditioning the Erdos-Renyi graph $G(N,p)$ to be acyclic. We describe scaling limits for the largest components of $F(N,p)$ and $F(N,m)$, in the critical window $p=N^{-1}+O(N^{-4/3})$ or $m=N/2+O(N^{2/3})$. Aldous described a scaling limit for the largest components of $G(N,p)$ within the critical window in terms of the excursion lengths of a reflected Brownian motion with time-dependent drift. Our scaling limit for critical random forests is of a similar nature, but now based on a reflected diffusion whose drift depends on space as well as on time.
• ### Stability of Service under Time-of-Use Pricing(1704.02364)

April 7, 2017 cs.GT
We consider "time-of-use" pricing as a technique for matching supply and demand of temporal resources with the goal of maximizing social welfare. Relevant examples include energy, computing resources on a cloud computing platform, and charging stations for electric vehicles, among many others. A client/job in this setting has a window of time during which he needs service, and a particular value for obtaining it. We assume a stochastic model for demand, where each job materializes with some probability via an independent Bernoulli trial. Given a per-time-unit pricing of resources, any realized job will first try to get served by the cheapest available resource in its window and, failing that, will try to find service at the next cheapest available resource, and so on. Thus, the natural stochastic fluctuations in demand have the potential to lead to cascading overload events. Our main result shows that setting prices so as to optimally handle the {\em expected} demand works well: with high probability, when the actual demand is instantiated, the system is stable and the expected value of the jobs served is very close to that of the optimal offline algorithm.
• ### Optimal low-rank approximations of Bayesian linear inverse problems(1407.3463)

July 6, 2015 math.NA, stat.CO, stat.ME
In the Bayesian approach to inverse problems, data are often informative, relative to the prior, only on a low-dimensional subspace of the parameter space. Significant computational savings can be achieved by using this subspace to characterize and approximate the posterior distribution of the parameters. We first investigate approximation of the posterior covariance matrix as a low-rank update of the prior covariance matrix. We prove optimality of a particular update, based on the leading eigendirections of the matrix pencil defined by the Hessian of the negative log-likelihood and the prior precision, for a broad class of loss functions. This class includes the F\"{o}rstner metric for symmetric positive definite matrices, as well as the Kullback-Leibler divergence and the Hellinger distance between the associated distributions. We also propose two fast approximations of the posterior mean and prove their optimality with respect to a weighted Bayes risk under squared-error loss. These approximations are deployed in an offline-online manner, where a more costly but data-independent offline calculation is followed by fast online evaluations. As a result, these approximations are particularly useful when repeated posterior mean evaluations are required for multiple data sets. We demonstrate our theoretical results with several numerical examples, including high-dimensional X-ray tomography and an inverse heat conduction problem. In both of these examples, the intrinsic low-dimensional structure of the inference problem can be exploited while producing results that are essentially indistinguishable from solutions computed in the full space.
• ### Likelihood-informed dimension reduction for nonlinear inverse problems(1403.4680)

July 15, 2014 math.NA, stat.CO, stat.ME
The intrinsic dimensionality of an inverse problem is affected by prior information, the accuracy and number of observations, and the smoothing properties of the forward operator. From a Bayesian perspective, changes from the prior to the posterior may, in many problems, be confined to a relatively low-dimensional subspace of the parameter space. We present a dimension reduction approach that defines and identifies such a subspace, called the "likelihood-informed subspace" (LIS), by characterizing the relative influences of the prior and the likelihood over the support of the posterior distribution. This identification enables new and more efficient computational methods for Bayesian inference with nonlinear forward models and Gaussian priors. In particular, we approximate the posterior distribution as the product of a lower-dimensional posterior defined on the LIS and the prior distribution marginalized onto the complementary subspace. Markov chain Monte Carlo sampling can then proceed in lower dimensions, with significant gains in computational efficiency. We also introduce a Rao-Blackwellization strategy that de-randomizes Monte Carlo estimates of posterior expectations for additional variance reduction. We demonstrate the efficiency of our methods using two numerical examples: inference of permeability in a groundwater system governed by an elliptic PDE, and an atmospheric remote sensing problem based on Global Ozone Monitoring System (GOMOS) observations.
• ### A computational framework for infinite-dimensional Bayesian inverse problems: Part II. Stochastic Newton MCMC with application to ice sheet flow inverse problems(1308.6221)

We address the numerical solution of infinite-dimensional inverse problems in the framework of Bayesian inference. In the Part I companion to this paper (arXiv.org:1308.1313), we considered the linearized infinite-dimensional inverse problem. Here in Part II, we relax the linearization assumption and consider the fully nonlinear infinite-dimensional inverse problem using a Markov chain Monte Carlo (MCMC) sampling method. To address the challenges of sampling high-dimensional pdfs arising from Bayesian inverse problems governed by PDEs, we build on the stochastic Newton MCMC method. This method exploits problem structure by taking as a proposal density a local Gaussian approximation of the posterior pdf, whose construction is made tractable by invoking a low-rank approximation of its data misfit component of the Hessian. Here we introduce an approximation of the stochastic Newton proposal in which we compute the low-rank-based Hessian at just the MAP point, and then reuse this Hessian at each MCMC step. We compare the performance of the proposed method to the original stochastic Newton MCMC method and to an independence sampler. The comparison of the three methods is conducted on a synthetic ice sheet inverse problem. For this problem, the stochastic Newton MCMC method with a MAP-based Hessian converges at least as rapidly as the original stochastic Newton MCMC method, but is far cheaper since it avoids recomputing the Hessian at each step. On the other hand, it is more expensive per sample than the independence sampler; however, its convergence is significantly more rapid, and thus overall it is much cheaper. Finally, we present extensive analysis and interpretation of the posterior distribution, and classify directions in parameter space based on the extent to which they are informed by the prior or the observations.
• ### Long-range last-passage percolation on the line(1104.2420)

Oct. 16, 2013 math.PR
We consider directed last-passage percolation on the random graph G = (V,E) where V = Z and each edge (i,j), for i < j, is present in E independently with some probability 0 < p <= 1. To every present edge (i,j) we attach i.i.d. random weights v_{i,j} > 0. We are interested in the behaviour of w_{0,n}, which is the maximum weight of all directed paths from 0 to n, as n tends to infinity. We see two very different types of behaviour, depending on whether E[v_{i,j}^2] is finite or infinite. In the case where E[v_{i,j}^2] is finite we show that the process has a certain regenerative structure, and prove a strong law of large numbers and, under an extra assumption, a functional central limit theorem. In the situation where E[v_{i,j}^2] is infinite we obtain scaling laws and asymptotic distributions expressed in terms of a "continuous last-passage percolation" model on [0,1]; these are related to corresponding results for two-dimensional last-passage percolation with heavy-tailed weights obtained by Hambly and Martin.
• ### A computational framework for infinite-dimensional Bayesian inverse problems. Part I: The linearized case, with application to global seismic inversion(1308.1313)

Aug. 6, 2013 math.NA, stat.CO, stat.ME, math.OC
We present a computational framework for estimating the uncertainty in the numerical solution of linearized infinite-dimensional statistical inverse problems. We adopt the Bayesian inference formulation: given observational data and their uncertainty, the governing forward problem and its uncertainty, and a prior probability distribution describing uncertainty in the parameter field, find the posterior probability distribution over the parameter field. The prior must be chosen appropriately in order to guarantee well-posedness of the infinite-dimensional inverse problem and facilitate computation of the posterior. Furthermore, straightforward discretizations may not lead to convergent approximations of the infinite-dimensional problem. And finally, solution of the discretized inverse problem via explicit construction of the covariance matrix is prohibitive due to the need to solve the forward problem as many times as there are parameters. Our computational framework builds on the infinite-dimensional formulation proposed by Stuart (A. M. Stuart, Inverse problems: A Bayesian perspective, Acta Numerica, 19 (2010), pp. 451-559), and incorporates a number of components aimed at ensuring a convergent discretization of the underlying infinite-dimensional inverse problem. The framework additionally incorporates algorithms for manipulating the prior, constructing a low rank approximation of the data-informed component of the posterior covariance operator, and exploring the posterior that together ensure scalability of the entire framework to very high parameter dimensions. We demonstrate this computational framework on the Bayesian solution of an inverse problem in 3D global seismic wave propagation with hundreds of thousands of parameters.
• ### Avoidance Coupling(1112.3304)

July 10, 2013 math.PR
We examine the question of whether a collection of random walks on a graph can be coupled so that they never collide. In particular, we show that on the complete graph on n vertices, with or without loops, there is a Markovian coupling keeping apart Omega(n/log n) random walks, taking turns to move in discrete time.
• ### Berlekamp's Switching Game on Finite Projective and Affine Planes(1208.1649)

Aug. 8, 2012 math.CO, cs.DM
I adapt Berlekamp's light bulb switching game to finite projective plans and finite affine planes, then find the worst arrangement of lit bulbs for planes of even and odd orders. The results are then extended from the planes to spaces of higher dimension.
• ### Stochastic Domination and Comb Percolation(1201.6373)

Jan. 30, 2012 math.PR
There exists a Lipschitz embedding of a d-dimensional comb graph (consisting of infinitely many parallel copies of Z^{d-1} joined by a perpendicular copy) into the open set of site percolation on Z^d, whenever the parameter p is close enough to 1 or the Lipschitz constant is sufficiently large. This is proved using several new results and techniques involving stochastic domination, in contexts that include a process of independent overlapping intervals on Z, and first-passage percolation on general graphs.
• ### Thermally Activated Magnetization and Resistance Decay during Near Ambient Temperature Aging of Co Nanoflakes in a Confining Semi-metallic Environment(1109.0506)

Oct. 12, 2011 cond-mat.mes-hall
We report the observation of magnetic and resistive aging in a self assembled nanoparticle system produced in a multilayer Co/Sb sandwich. The aging decays are characterized by an initial slow decay followed by a more rapid decay in both the magnetization and resistance. The decays are large accounting for almost 70% of the magnetization and almost 40% of the resistance for samples deposited at 35 $^oC$. For samples deposited at 50 $^oC$ the magnetization decay accounts for $\sim 50%$ of the magnetization and 50% of the resistance. During the more rapid part of the decay, the concavity of the slope of the decay changes sign and this inflection point can be used to provide a characteristic time. The characteristic time is strongly and systematically temperature dependent, ranging from $\sim1$x$10^2 s$ at 400K to $\sim3$x$10^5 s$ at 320K in samples deposited at $35 ^oC$. Samples deposited at 50 $^oC$ displayed a 7-8 fold increase in the characteristic time (compared to the $35 ^oC$ samples) for a given aging temperature, indicating that this timescale may be tunable. Both the temperature scale and time scales are in potentially useful regimes. Pre-Aging, Scanning Tunneling Microscopy (STM) reveals that the Co forms in nanoscale flakes. During aging the nanoflakes melt and migrate into each other in an anisotropic fashion forming elongated Co nanowires. This aging behavior occurs within a confined environment of the enveloping Sb layers. The relationship between the characteristic time and aging temperature fits an Arrhenius law indicating activated dynamics.
• ### Multi-type TASEP in discrete time(1002.3539)

March 27, 2010 math.PR
The TASEP (totally asymmetric simple exclusion process) is a basic model for an one-dimensional interacting particle system with non-reversible dynamics. Despite the simplicity of the model it shows a very rich and interesting behaviour. In this paper we study some aspects of the TASEP in discrete time and compare the results to the recently obtained results for the TASEP in continuous time. In particular we focus on stationary distributions for multi-type models, speeds of second-class particles, collision probabilities and the "speed process". In discrete time, jump attempts may occur at different sites simultaneously, and the order in which these attempts are processed is important; we consider various natural update rules.