Biased random walks

DOI10.1007/BF01300124MaRDI QIDQ1912749zbMATH OpenOpenAlexFDO

Authors Yossi Azar, Andrei Broder, Anna R. Karlin, Nathan Linial, Steven J. Phillips

Publication date 16 September 1996

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01300124

zbMATH Keywords

algorithms for computing the optimal controller strategylong-term behavior of a random walk on a finite graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Sums of independent random variables; random walks (60G50) Markov and semi-Markov decision processes (90C40)

Recommendations

• The cover time of a biased random walk on \(G_{n,p}\)
• Random walks on weighted graphs and applications to on-line algorithms
• scientific article; zbMATH DE number 878897
• Fair and biased random walks on undirected graphs and related entropies
• The power of two choices for random walks

Cites work

• scientific article; zbMATH DE number 3776305 (Why is no real title available?)
• scientific article; zbMATH DE number 3288876 (Why is no real title available?)
• Biased random walks
• Coin-Flipping Games Immune against Linear-Sized Coalitions
• Finite state Markovian decision processes
• Generating quasi-random sequences from semi-random sources
• Some extremal problems arising from discrete control processes
• The influence of large coalitions

Cited in

(14)

• Biased random walk in a one-dimensional percolation model
• Fair and biased random walks on undirected graphs and related entropies
• Memoryless search algorithms in a network with faulty advice
• scientific article; zbMATH DE number 2166523 (Why is no real title available?)
• On the approximation of one Markov chain by another
• The Metropolis algorithm for graph bisection
• Random walk with persistence and external bias
• Biased random walks
• Time Dependent Biased Random Walks
• Premature sampling in random walks
• The power of two choices for random walks
• Efficient learning of typical finite automata from random walks
• Representation of elements of a sequence by sumsets
• Measuring bias in cyclic random walks

This page was built for publication: Biased random walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1912749)