Yuval Peres

NeurIPS Conference 2019 Conference Paper

Staying up to Date with Online Content Changes Using Reinforcement Learning for Scheduling

• Andrey Kolobov
• Yuval Peres
• Cheng Lu
• Eric Horvitz

From traditional Web search engines to virtual assistants and Web accelerators, services that rely on online information need to continually keep track of remote content changes by explicitly requesting content updates from remote sources (e. g. , web pages). We propose a novel optimization objective for this setting that has several practically desirable properties, and efficient algorithms for it with optimality guarantees even in the face of mixed content change observability and initially unknown change model parameters. Experiments on 18. 5M URLs crawled daily for 14 weeks show significant advantages of this approach over prior art.

SODA Conference 2018 Conference Paper

Comparing mixing times on sparse random graphs

• Anna Ben-Hamou
• Eyal Lubetzky
• Yuval Peres

It is natural to expect that nonbacktracking random walk will mix faster than simple random walks, but so far this has only been proved in regular graphs. To analyze typical irregular graphs, let G be a random graph on n vertices with minimum degree 3 and a degree distribution that has exponential tails. We determine the precise worst-case mixing time for simple random walk on G, and show that, with high probability, it exhibits cutoff at time h –1 log n, where h is the asymptotic entropy for simple random walk on a Galton-Watson tree that approximates G locally. (Previously this was only known for typical starting points.) Furthermore, we show this asymptotic mixing time is strictly larger than the mixing time of nonbacktracking walk, via a delicate comparison of entropies on the Galton-Watson tree.

SODA Conference 2018 Conference Paper

Estimating graph parameters via random walks with restarts

• Anna Ben-Hamou
• Roberto I. Oliveira 0001
• Yuval Peres

In this paper we discuss the problem of estimating graph parameters from a random walk with restarts. In this setting, an algorithm observes the trajectory of a random walk over an unknown graph G, starting from a vertex x. The algorithm also sees the degrees along the trajectory. The only other power that the algorithm has is to request that the random walk be reset to its initial state at any given time, based on what it has seen so far. Our main results are as follows. For regular graphs G, one can estimate the number of vertices n G and the ℓ 2 mixing time of G from x in steps, where is the uniform mixing time of the random walk on G. The algorithm is based on the number of intersections of random walk paths X, Y, ie. the number of times ( t, s ) such that X t = Y s. Our method improves on previous methods by various authors which only consider collisions (ie. times t with X t = Y t ). We also show that the time complexity of our algorithm is optimal (up to log factors) for 3-regular graphs with prescribed mixing times. For general graphs, we adapt the intersections algorithm to compute the number of edges m G and the ℓ 2 mixing time from the starting vertex x in steps. Under mild additional assumptions (which hold e. g. for sparse graphs) the number of vertices can also be estimated by this time. Finally, we show that these algorithms, which may take sublinear time, have a fundamental limitation: it is not possible to devise a sublinear stopping time at which one can be reasonably sure that our parameters are well estimated. On the other hand, we show that, given either ma or the mixing time of G, we can compute the “other parameter” with a self-stopping algorithm.

SODA Conference 2018 Conference Paper

Exponentially slow mixing in the mean-field Swendsen-Wang dynamics

• Reza Gheissari
• Eyal Lubetzky
• Yuval Peres

Swendsen-Wang dynamics for the Potts model was proposed in the late 1980's as an alternative to single-site heat-bath dynamics, in which global updates allow this MCMC sampler to switch between metastable states and ideally mix faster. Gore and Jerrum (1997) found that this dynamics may in fact exhibit slow mixing: they showed that, for the Potts model with q ≥ 3 colors on the complete graph on n vertices at the critical point β c ( q ), Swendsen–Wang dynamics has. Galanis et al. (2015) showed that t MIX ≥ exp( cn 1/3 ) throughout the critical window ( β s, βs ) around β c, and Blanca and Sinclair (2015) established that in the critical window for corresponding mean-field FK model, which implied the same bound for Swendsen–Wang via known comparison estimates. In both cases, an upper bound of t MIX ≤ exp( c ′ n ) was known. Here we show that the mixing time is truly exponential in n: namely, t MIX ≥ exp( cn ) for Swendsen–Wang dynamics when q ≥ 3 and β ∊ ( β s, β S ), and the same bound holds for the related MCMC samplers for the mean-field FK model when q > 2.

FOCS Conference 2018 Conference Paper

Testing Graph Clusterability: Algorithms and Lower Bounds

• Ashish Chiplunkar
• Michael Kapralov
• Sanjeev Khanna
• Aida Mousavifar
• Yuval Peres

We consider the problem of testing graph cluster structure: given access to a graph G = (V, E), can we quickly determine whether the graph can be partitioned into a few clusters with good inner conductance, or is far from any such graph? This is a generalization of the well-studied problem of testing graph expansion, where one wants to distinguish between the graph having good expansion (i. e. being a good single cluster) and the graph having a sparse cut (i. e. being a union of at least two clusters). A recent work of Czumaj, Peng, and Sohler (STOC'15) gave an ingenious sublinear time algorithm for testing k-clusterability in time Õ(n^1/2 poly(k)). Their algorithm implicitly embeds a random sample of vertices of the graph into Euclidean space, and then clusters the samples based on estimates of Euclidean distances between the points. This yields a very efficient testing algorithm, but only works if the cluster structure is very strong: it is necessary to assume that the gap between conductances of accepted and rejected graphs is at least logarithmic in the size of the graph G. In this paper we show how one can leverage more refined geometric information, namely angles as opposed to distances, to obtain a sublinear time tester that works even when the gap is a sufficiently large constant. Our tester is based on the singular value decomposition of a natural matrix derived from random walk transition probabilities from a small sample of seed nodes. We complement our algorithm with a matching lower bound on the query complexity of testing clusterability. Our lower bound is based on a novel property testing problem, which we analyze using Fourier analytic tools. As a byproduct of our techniques, we also achieve new lower bounds for the problem of approximating MAX-CUT value in sublinear time.

FOCS Conference 2017 Conference Paper

Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice

• Yuval Peres
• Alex Zhai

The deletion channel takes as input a bit string x ∈ {0, 1} n, and deletes each bit independently with probability q, yielding a shorter string. The trace reconstruction problem is to recover an unknown string x from many independent outputs (called “traces”) of the deletion channel applied to x. We show that if x is drawn uniformly at random and q O(log1/2 n) traces suffice to reconstruct x with high probability. The previous best bound, established in 2008 by Holenstein, Mitzenmacher, Panigrahy, and Wieder [1], uses n O(1) traces and only applies for q less than a smaller threshold (it seems that q <; 0. 07 is needed). Our algorithm combines several ideas: 1) an alignment scheme for “greedily” fitting the output of the deletion channel as a subsequence of the input; 2) a version of the idea of “anchoring” used in [1]; and 3) complex analysis techniques from recent work of Nazarov and Peres [2] and De, O'Donnell, and Servedio [3].

STOC Conference 2017 Conference Paper

Local max-cut in smoothed polynomial time

• Omer Angel
• Sébastien Bubeck
• Yuval Peres
• Fan Wei

In 1988, Johnson, Papadimitriou and Yannakakis wrote that "Practically all the empirical evidence would lead us to conclude that finding locally optimal solutions is much easier than solving NP-hard problems". Since then the empirical evidence has continued to amass, but formal proofs of this phenomenon have remained elusive. A canonical (and indeed complete) example is the local max-cut problem, for which no polynomial time method is known. In a breakthrough paper, Etscheid and Röglin proved that the smoothed complexity of local max-cut is quasi-polynomial, i.e., if arbitrary bounded weights are randomly perturbed, a local maximum can be found in ϕ n O (log n ) steps where ϕ is an upper bound on the random edge weight density. In this paper we prove smoothed polynomial complexity for local max-cut, thus confirming that finding local optima for max-cut is much easier than solving it.

STOC Conference 2017 Conference Paper

Trace reconstruction with exp(O(n 1/3 )) samples

• Fedor Nazarov
• Yuval Peres

In the trace reconstruction problem, an unknown bit string x ∈ {0,1} n is observed through the deletion channel, which deletes each bit of x with some constant probability q , yielding a contracted string x . How many independent copies of x are needed to reconstruct x with high probability? Prior to this work, the best upper bound, due to Holenstein, Mitzenmacher, Panigrahy, and Wieder (2008), was exp( O ( n 1/2 )). We improve this bound to exp( O ( n 1/3 )) using statistics of individual bits in the output and show that this bound is sharp in the restricted model where this is the only information used. Our method, that uses elementary complex analysis, can also handle insertions. Similar results were obtained independently and simultaneously by Anindya De, Ryan O'Donnell and Rocco Servedio.

SODA Conference 2016 Conference Paper

Towards Optimal Algorithms for Prediction with Expert Advice

• Nikolai Gravin
• Yuval Peres
• Balasubramanian Sivan

We study the classical problem of prediction with expert advice in the adversarial setting with a geometric stopping time. In 1965, Cover gave the optimal algorithm for the case of 2 experts. In this paper, we design the optimal algorithm, adversary and regret for the case of 3 experts. Further, we show that the optimal algorithm for 2 and 3 experts is a probability matching algorithm (analogous to Thompson sampling) against a particular randomized adversary. Remarkably, our proof shows that the probability matching algorithm is not only optimal against this particular randomized adversary, but also minimax optimal. Our analysis develops upper and lower bounds simultaneously, analogous to the primal-dual method. Our analysis of the optimal adversary goes through delicate asymptotics of the random walk of a particle between multiple walls. We use the connection we develop to random walks to derive an improved algorithm and regret bound for the case of 4 experts, and, provide a general framework for designing the optimal algorithm and adversary for an arbitrary number of experts.

ICML Conference 2015 Conference Paper

Approval Voting and Incentives in Crowdsourcing

• Nihar B. Shah
• Dengyong Zhou
• Yuval Peres

The growing need for labeled training data has made crowdsourcing an important part of machine learning. The quality of crowdsourced labels is, however, adversely affected by three factors: (1) the workers are not experts; (2) the incentives of the workers are not aligned with those of the requesters; and (3) the interface does not allow workers to convey their knowledge accurately, by forcing them to make a single choice among a set of options. In this paper, we address these issues by introducing approval voting to utilize the expertise of workers who have partial knowledge of the true answer, and coupling it with a ("strictly proper") incentive-compatible compensation mechanism. We show rigorous theoretical guarantees of optimality of our mechanism together with a simple axiomatic characterization. We also conduct preliminary empirical studies on Amazon Mechanical Turk which validate our approach.

SODA Conference 2015 Conference Paper

Characterization of cutoff for reversible Markov chains

• Riddhipratim Basu
• Jonathan Hermon
• Yuval Peres

SODA Conference 2015 Conference Paper

Perfect Bayesian Equilibria in Repeated Sales

• Nikhil R. Devanur
• Yuval Peres
• Balasubramanian Sivan

A special case of Myerson's classic result describes the revenue-optimal equilibrium when a seller offers a single item to a buyer. We study a natural repeated sales extension of this model: a seller offers to sell a single fresh copy of an item to the same buyer every day via a posted price. The buyer's value for the item is unknown to the seller but is drawn initially from a publicly known distribution F and remains the same throughout. One key aspect of this game is revelation of the buyer's type through his actions: while the seller might try to learn this value to extract more revenue, the buyer is motivated to hide it to induce lower prices. If the seller is able to commit to future prices, then it is known that the best he can do is extract the Myerson optimal revenue each day. In a more realistic scenario, the seller is unable to commit and must play a perfect Bayesian equilibrium. It is known that not committing to future prices does not help the seller. Thus extracting Myerson optimal revenue each day is a natural upper bound and revenue benchmark in a setting without commitment. We study this setting without commitment and find several suprises. First, if the horizon is fixed, previous work showed that an equilibrium always exists, and all equilibria yield a very low revenue, often times only a constant amount of revenue. This is unintuitive and a far cry from the linearly growing benchmark of obtaining Myerson optimal revenue each day. Our first result shows that this is because the buyer strategies in these equilibria are necessarily unnatural. We restrict to a natural class of buyer strategies, which we call threshold strategies, and show that pure strategy threshold equilibria rarely exist. This offers an explanation for the non-prevalence of bizarre outcomes predicted by previous results. Second, if the seller can commit not to raise prices upon purchase, while still retaining the possibility of lowering prices in future, we recover the natural threshold equilibria by showing that they exist for a large class of distributions including the power law family of distributions. As an example, if the distribution F is uniform in [0, 1], the seller can extract revenue of order in n rounds as opposed to the constant revenue obtainable when he is unable to make any commitments. Finally, we consider the infinite horizon game with partial commitment, where both the seller and the buyer discount the future utility by a factor of 1 – δ ∊ [0, 1). When the value distribution is uniform in [0, 1], there exists a threshold equilibrium with expected revenue at least of the Myerson optimal revenue benchmark. Under some mild assumptions, this equilibrium is also unique.

SODA Conference 2015 Conference Paper

Surprise probabilities in Markov chains

• James Norris
• Yuval Peres
• Alex Zhai

In a Markov chain started at a state x, the hitting time τ ( y ) is the first time that the chain reaches another state y. We study the probability P x ( τ ( y ) = t ) that the first visit to y occurs precisely at a given time t. Informally speaking, the event that a new state is visited at a large time t may be considered a “surprise”. We prove the following three bounds: In any Markov chain with n states, In a reversible chain with n states, For random walk on a simple graph with n ≥ 2 vertices, We construct examples showing that these bounds are close to optimal. The main feature of our bounds is that they require very little knowledge of the structure of the Markov chain. To prove the bound for random walk on graphs, we establish the following estimate conjectured by Aldous, Ding and Oveis-Gharan (private communication): For random walk on an n -vertex graph, for every initial vertex x,

STOC Conference 2014 Conference Paper

Bandits with switching costs: T 2/3 regret

• Ofer Dekel
• Jian Ding
• Tomer Koren
• Yuval Peres

We study the adversarial multi-armed bandit problem in a setting where the player incurs a unit cost each time he switches actions. We prove that the player's T -round minimax regret in this setting is [EQUATION], thereby closing a fundamental gap in our understanding of learning with bandit feedback. In the corresponding full-information version of the problem, the minimax regret is known to grow at a much slower rate of Θ(√ T ). The difference between these two rates provides the first indication that learning with bandit feedback can be significantly harder than learning with full information feedback (previous results only showed a different dependence on the number of actions, but not on T .) In addition to characterizing the inherent difficulty of the multi-armed bandit problem with switching costs, our results also resolve several other open problems in online learning. One direct implication is that learning with bandit feedback against bounded-memory adaptive adversaries has a minimax regret of [EQUATION]. Another implication is that the minimax regret of online learning in adversarial Markov decision processes (MDPs) is [EQUATION]. The key to all of our results is a new randomized construction of a multi-scale random walk, which is of independent interest and likely to prove useful in additional settings.

STOC Conference 2011 Conference Paper

Cover times, blanket times, and majorizing measures

• Jian Ding
• James R. Lee
• Yuval Peres

We exhibit a strong connection between cover times of graphs, Gaussian processes, and Talagrand's theory of majorizing measures. In particular, we show that the cover time of any graph G is equivalent, up to universal constants, to the square of the expected maximum of the Gaussian free field on G, scaled by the number of edges in G. This allows us to resolve a number of open questions. We give a deterministic polynomial-time algorithm that computes the cover time to within an O(1) factor for any graph, answering a question of Aldous and Fill (1994). We also positively resolve the blanket time conjectures of Winkler and Zuckerman (1996), showing that for any graph, the blanket and cover times are within an O(1) factor. The best previous approximation factor for both these problems was O((log log n) 2 ) for n-vertex graphs, due to Kahn, Kim, Lovasz, and Vu (2000).

SODA Conference 2011 Conference Paper

Mobile Geometric Graphs: Detection, Coverage and Percolation

• Yuval Peres
• Alistair Sinclair
• Perla Sousi
• Alexandre Stauffer

Static wireless networks are by now quite well understood mathematically through the random geometric graph model. By contrast, there are relatively few rigorous results on the practically important case of mobile networks. In this paper we consider a natural extension of the random geometric graph model to the mobile setting by allowing nodes to move in space according to Brownian motion. We study three fundamental questions in this model: detection (the time until a given target point—which may be either fixed or moving—is detected by the network), coverage (the time until all points inside a finite box are detected by the network), and percolation (the time until a given node is able to communicate with the giant component of the network). We derive precise asymptotics for these problems by combining ideas from stochastic geometry, coupling and multi-scale analysis. We also give an application of our results to analyze the time to broadcast a message in a mobile network.

FOCS Conference 2010 Conference Paper

All-Pairs Shortest Paths in O(n 2 ) Time with High Probability

• Yuval Peres
• Dmitry Sotnikov
• Benny Sudakov
• Uri Zwick

We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices whose edge weights are chosen independently and uniformly at random from [0, 1] is O(n 2 ), in expectation and with high probability. This resolves a long standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano. The analysis relies on a proof that the number of locally shortest paths in such randomly weighted graphs is O(n 2 ), in expectation and with high probability. We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in O(log 2 n) expected time.

SODA Conference 2010 Conference Paper

The (1 + beta)-Choice Process and Weighted Balls-into-Bins

• Yuval Peres
• Kunal Talwar
• Udi Wieder

FOCS Conference 2009 Conference Paper

Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks

• Yossi Azar
• Benjamin E. Birnbaum
• L. Elisa Celis
• Nikhil R. Devanur
• Yuval Peres

Bargaining games on exchange networks have been studied by both economists and sociologists. A Balanced Outcome for such a game is an equilibrium concept that combines notions of stability and fairness. In a recent paper, Kleinberg and Tardos introduced balanced outcomes to the computer science community and provided a polynomial-time algorithm to compute the set of such outcomes. Their work left open a pertinent question: are there natural, local dynamics that converge quickly to a balanced outcome? In this paper, we provide a partial answer to this question by showing that simple edge-balancing dynamics converge to a balanced outcome whenever one exists.

STOC Conference 2009 Conference Paper

Finding sparse cuts locally using evolving sets

• Reid Andersen
• Yuval Peres

A local graph partitioning algorithm finds a set of vertices with small conductance (i.e.~a sparse cut) by adaptively exploring a large graph G, starting from a specified vertex. For the algorithm to be local, its complexity must be bounded in terms of the size of the set it outputs, with at most a weak dependence on n, the number of vertices in G. Previous local partitioning algorithms find sparse cuts using random walks and personalized PageRank. In this paper, we introduce a randomized local partitioning algorithm that finds a sparse cut by simulating the volume-biased evolving set process , which is a Markov chain on sets of vertices. We prove that for any set of vertices A that has conductance at most φ, and for at least half of the starting vertices in A, our algorithm will output (with probability at least half) a set of conductance O(φ 1/2 log 1/2 n). The complexity of a local partitioning algorithm is measured by its work/volume ratio, which is the ratio between the computational complexity of the algorithm on a given run, and the volume of the set output. We prove that for our algorithm, the expected value of the work/volume ratio is polylognoparen(φ -1/2 ). The best previous local partitioning algorithm, due to Andersen, Chung, and Lang, has the same approximation guarantee but a larger work/volume ratio of polylognoparen(φ -1 ). As an application of our local partitioning algorithm, we construct a fast algorithm for finding balanced cuts. The resulting algorithm takes as input a graph and a fixed value of φ, has complexity polylog{m+nφ -1/2 ), and returns a cut with conductance O(φ 1/2 log 1/2 n) and volume at least v φ /2, where v φ is the volume of the largest set in the graph with conductance at most φ.

SODA Conference 2009 Conference Paper

The unreasonable effectiveness of martingales

• Yuval Peres

SODA Conference 2008 Conference Paper

Maximum overhang

• Mike Paterson
• Yuval Peres
• Mikkel Thorup
• Peter Winkler 0001
• Uri Zwick

FOCS Conference 2008 Conference Paper

Noise Tolerance of Expanders and Sublinear Expander Reconstruction

• Satyen Kale
• Yuval Peres
• C. Seshadhri 0001

We consider the problem of online sublinear expander reconstruction and its relation to random walks in ``noisy" expanders. Given access to an adjacency list representation of a bounded-degree graph G, we want to convert this graph into a bounded-degree expander G' changing G as little aspossible. The graph G' will be output by a distributed filter: this is sublinear time procedure that given a query vertex, outputs all its neighbors in G', and can do so even in a distributed manner, ensuring consistency in all the answers. One of the main tools in our analysis is a result on the behavior of random walks in graph that are almost expanders: graphs that are formed by arbitrarily connecting a small unknown graph (the noise) to a large expander. We show that a random walk from almost any vertex in the expander part will have fast mixing properties, in the general setting of irreducible finite Markov chains. We alsodesign sublinear time procedures to distinguish vertices of the expander part from those in the noise part, and use this procedure in the reconstruction algorithm.

FOCS Conference 2007 Conference Paper

Mixing Time Power Laws at Criticality

• Yun Long
• Asaf Nachmias
• Yuval Peres

We study the mixing time of some Markov chains converging to critical physical models. These models are indexed by a parameter beta and there exists some critical value beta c where the model undergoes a phase transition. According to physics lore, the mixing time of such Markov chains is often of logarithmic order outside the critical regime, when beta ne beta c, and satisfies-some power law at criticality, when beta = beta c. We prove this in the two following settings: 1. Lazy random walk on the critical percolation cluster of "mean-field" graphs, which include the complete graph and random d-regular graphs. The critical mixing time here is of order Theta(n). This answers a question of Benjamini, Kozma and Wormald. 2. Swendsen-Wang dynamics on the complete, graph. The critical mixing time, here is of order Theta(n 1/4 ). This improves results of Cooper, Dyer, Frieze and Rue. In both settings, the main tool is understanding the Markov chain dynamics via properties of critical percolation on the underlying graph.

SODA Conference 2006 Conference Paper

Trees and Markov convexity

• James R. Lee
• Assaf Naor
• Yuval Peres

FOCS Conference 2004 Conference Paper

Shuffling by Semi-Random Transpositions

• Elchanan Mossel
• Yuval Peres
• Alistair Sinclair

In the cyclic-to-random shuffle, we are given n cards arranged in a circle. At step k, we exchange the kth card along the circle with a uniformly chosen random card. The problem of determining the mixing time of the cyclic-to-random shuffle was raised by Aldous and Diaconis in 1986. Mironov used this shuffle as a model for the cryptographic system known as RC4, and proved an upper bound of O(n log n) for the mixing time. We prove a matching lower bound, thus establishing that the mixing time is indeed of order /spl Theta/(n log n). We also prove an upper bound of O(n log n) for the mixing time of any "semirandom transposition shuffle", i. e. , any shuffle in which a random card is exchanged with another card chosen according to an arbitrary (deterministic or random) rule. To prove our lower bound, we exhibit an explicit complex-valued test function which typically takes very different values for permutations arising from few iterations of the cyclic-to-random-shuffle and for uniform random permutations. Perhaps surprisingly, the proof hinges on the fact that the function e/sup z/ - 1 has nonzero fixed points in the complex plane. A key insight from our work is the importance of complex analysis tools for uncovering structure in nonreversible Markov chains.

STOC Conference 2003 Conference Paper

Evolving sets and mixin

• Ben Morris 0001
• Yuval Peres

FOCS Conference 2003 Conference Paper

On the Maximum Satisfiability of Random Formulas

• Dimitris Achlioptas
• Assaf Naor
• Yuval Peres

Maximum satisfiability is a canonical NP-complete problem that appears empirically hard for random instances. At the same time, it is rapidly becoming a canonical problem for statistical physics. In both of these realms, evaluating new ideas relies crucially on knowing the maximum number of clauses one can typically satisfy in a random k-CNF formula. In this paper we give asymptotically tight estimates for this quantity. Our result gives very tight bounds for the fraction of satisfiable clauses in a random k-CNF. In particular, for k > 2 it improves upon all previously known such bound.

STOC Conference 2003 Conference Paper

The threshold for random k-SAT is 2 k (ln 2 - O(k))

• Dimitris Achlioptas
• Yuval Peres

Let F k (n,m) be a random k -SAT formula on n variables formed by selecting uniformly and independently m out of all possible k -clauses. It is well-known that for r ≥ 2 k ln 2 , F k (n,rn) is unsatisfiable with probability 1-o(1) . We prove that there exists a sequence t k = O(k) such that for r ≥ 2 k ln 2 - t k , F k (n,rn) is satisfiable with probability 1-o(1) .Our technique yields an explicit lower bound for every k which for k > 3 improves upon all previously known bounds. For example, when k=10 our lower bound is 704.94 while the upper bound is 708.94.

UAI Conference 2002 Conference Paper

Decayed MCMC Filtering

• Bhaskara Marthi
• Hanna Pasula
• Stuart Russell 0001
• Yuval Peres

Filtering---estimating the state of a partially observable Markov process from a sequence of observations---is one of the most widely studied problems in control theory, AI, and computational statistics. Exact computation of the posterior distribution is generally intractable for large discrete systems and for nonlinear continuous systems, so a good deal of effort has gone into developing robust approximation algorithms. This paper describes a simple stochastic approximation algorithm for filtering called {em decayed MCMC}. The algorithm applies Markov chain Monte Carlo sampling to the space of state trajectories using a proposal distribution that favours flips of more recent state variables. The formal analysis of the algorithm involves a generalization of standard coupling arguments for MCMC convergence. We prove that for any ergodic underlying Markov process, the convergence time of decayed MCMC with inverse-polynomial decay remains bounded as the length of the observation sequence grows. We show experimentally that decayed MCMC is at least competitive with other approximation algorithms such as particle filtering.

FOCS Conference 2001 Conference Paper

Glauber Dynamics on Trees and Hyperbolic Graphs

• Claire Mathieu
• Elchanan Mossel
• Yuval Peres

We study discrete time Glauber dynamics for random configurations with local constraints (e. g. proper coloring, Ising and Potts models) on finite graphs with n vertices and of bounded degree. We show that the relaxation time (defined as the reciprocal of the spectral gap 1-/spl lambda//sub 2/) for the dynamics on trees and on certain hyperbolic graphs, is polynomial in n. For these hyperbolic graphs, this yields a general polynomial sampling algorithm for random configurations. We then show that if the relaxation time /spl tau//sub 2/ satisfies /spl tau//sub 2/=O(n), then the correlation coefficient, and the mutual information, between any local function (which depends only on the configuration in a fixed window) and the boundary conditions, decays exponentially in the distance between the window and the boundary. For the Ising model on a regular tree, this condition is sharp.