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

Sums of independent random variables; random walks (60G50) Graph theory (including graph drawing) in computer science (68R10) 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

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

Cited in

(16)

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

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)