Language：English   Publishing type：Research paper (scientific journal)   Publisher：Society for industrial and applied mathematics  

DOI： 10.1137/16M1087667

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

Motivated by a derandomization of Markov chain Monte Carlo (MCMC), this paper investigates a deterministic random walk, which is a deterministic process analogous to a random walk. There is some recent progress in the analysis of the vertex-wise discrepancy (i.e., Loo-discrepancy), while little is known about the total variation discrepancy (i.e., L-1-discrepancy), which plays an important role in the analysis of an FPRAS based on MCMC. This paper investigates the L-1-discrepancy between the expected number of tokens in a Markov chain and the number of tokens in its corresponding deterministic random walk. First, we give a simple but nontrivial upper bound O(mt*) of the L-1-discrepancy for any ergodic Markov chains, where m is the number of edges of the transition diagram and t* is the mixing time of the Markov chain. Then, we give a better upper bound O(m t*) for non-oblivious deterministic random walks, if the corresponding Markov chain is ergodic and lazy. We also present some lower bounds. (C) 2016 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.tcs.2016.11.017

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing  

In a voting process on a graph vertices revise their opinions in a distributed way based on the opinions of nearby vertices. The voting completes when the vertices reach consensus, that is, they all have the same opinion. The classic example is synchronous pull voting where at each step, each vertex adopts the opinion of a random neighbour. This very simple process, however, can be slow and the final opinion is not necessarily the one with the initial largest support. It was shown earlier that if there are initially only two opposing opinions, then both these drawbacks can be overcome by a synchronous two-sample voting, in which at each step each vertex considers its own opinion and the opinions of two random neighbours. If there are initially three or more opinions, a problem arises when there is no clear majority. One class of opinions may be largest (the plurality opinion), although its total size is less than that of two other opinions put together. We analyse the performance of the two-sample voting on d-regular graphs for this case. We show that, if the difference between the initial sizes A1 and A2 of the largest and second largest opinions is at least Cn max{ √ (log n)/A1, λ}, then the largest opinion wins in O((n log n)/A1) steps with high probability. Here C is a suitable constant and is the absolute second eigenvalue of transition matrix P = Adj(G)/d of a simple random walk on the graph G. Our bound generalizes the results of Becchetti et al. [SPAA 2014] for the related three-sample voting process on complete graphs. Our bound implies that if λ = o(1), then the two-sample voting can consistently converge to the largest opinion, even if A1-A2 = o(n). If λ is constant, we show that the case A1 -A2 = o(n) can be dealt with by sampling using short random walks. Finally, we give a simple and efficient push voting algorithm for the case when there are a number of large opinions and any of them is acceptable as the final winning opinion.

DOI： 10.4230/LIPIcs.DISC.2017.13

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：International Conference on Probabilistic, Combinatorial and Asymptotic Methods |rn|for the Analysis of Algorithms  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Society for Industrial and Applied Mathematics  

DOI： 10.1137/1.9781611974324.13

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Hungarian-Japanese Symposium|rn|on Discrete Mathematics and Its Applications  

DOI： 10.1137/16M1087667

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER INT PUBLISHING AG  

Distributed voting is a fundamental topic in distributed computing. In the standard model of pull voting, at each step every vertex chooses a neighbour uniformly at random and adopts its opinion. The voting is completed when all vertices hold the same opinion. In the simplest case, each vertex initially holds one of two different opinions. This partitions the vertices into arbitrary sets A and B. For many graphs, including regular graphs and irrespective of their expansion properties, if both A and B are sufficiently large sets, then pull voting requires Omega(n) expected steps, where n is the number of vertices of the graph.
In this paper we consider a related class of voting processes based on sampling two opinions. In the simplest case, every vertex v chooses two random neighbours at each step. If both these neighbours have the same opinion, then v adopts this opinion. Otherwise, v keeps its own opinion. Let G be a connected graph with n vertices and m edges. Let P be the transition matrix of a simple random walk on G with second largest eigenvalue lambda < 1/root 2. We show that if the initial imbalance in degree between the two opinions satisfies vertical bar d(A) - d(B)vertical bar/2m >= 2 lambda(2), then with high probability voting completes in O(log n) steps, and the opinion with the larger initial degree wins.
The condition that lambda < 1/root 2 includes many classes of expanders, for example random d-regular graphs where d >= 10. If however 1/root 2 <= lambda(P) <= 1 - epsilon for a constant epsilon > 0, or only a bound on the conductance of the graph is known, the sampling process can be modified so that voting still provably completes in O(log n) steps with high probability. The modification uses two sampling based on probing to a fixed depth O(1/epsilon) from any vertex.
In its most general form our voting process allows vertices to bias their sampling of opinions among their neighbours to achieve a desired outcome. This is done by allocating weights to edges.

DOI： 10.1007/978-3-662-48653-5_17

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

We consider the rotor-router mechanism for distributing particles in an undirected graph. If the last particle passing through a vertex v took an edge (v,u), then the next time a particle is at v, it will leave v along the next edge (v,w) according to a fixed cyclic order of edges adjacent to v. The system works in synchronized steps and when two or more particles meet at the same vertex, they coalesce into one particle. A k-particle configuration of such a system is stable, if it does not lead to any coalescing. For 2≤k≤n, we give the full characterization of stable k-particle configurations for cycles. We also show sufficient conditions for regular graphs with n vertices to admit n-particle stable configurations.

DOI： 10.1007/978-3-319-25258-2_31

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：SPRINGER-VERLAG BERLIN  

Markov chain Monte Carlo (MCMC) is a standard technique to sample from a target distribution by simulating Markov chains. In an analogous fashion to MCMC, this paper proposes a deterministic sampling algorithm based on deterministic random walk, such as the rotorrouter model (a.k.a. Propp machine). For the algorithm, we give an upper bound of the point-wise distance (i.e., infinity norm) between the "distributions" of a deterministic random walk and its corresponding Markov chain in terms of the mixing time of the Markov chain. As a result, for uniform sampling of #P-complete problems, such as 0-1 knapsack solutions, linear extensions, matchings, etc., for which rapidly mixing chains are known, our deterministic algorithm provides samples with a "distribution" with a point-wise distance at most epsilon from the target distribution, in time polynomial in the input size and epsilon(-1).

DOI： 10.1007/978-3-319-08783-2_3

Web of Science

researchmap

Language：Japanese  

CiNii Books

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap