Name
Abstract | ||
|---|---|---|
Many classical search problems can be cast in the following abstract framework: Given a finite set X and a subset M⊆X of marked elements, detect if M is empty or not, or find an element in M if there is any. When M is not empty, a naive approach to the finding problem is to repeatedly pick a uniformly random element of X until a marked element is sampled. A more sophisticated approach might use a Markov chain, that is a random walk on the state space X in order to generate the samples. In that case the resources spent for previous steps are often reused to generate the next sample. Random walks also model spatial search in physical regions where the possible moves are expressed by the edges of some specific graph. The hitting time of a Markov chain is the number of steps necessary to reach a marked element, starting from the stationary distribution of the chain. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-13182-0_33 | CSR |
Keywords | Field | DocType |
random walk,classical search problem,finite set x,model spatial search,search algorithm,random element,state space x,naive approach,markov chain,subset m,marked element,hitting time,stationary distribution,state space | Random element,Discrete mathematics,Combinatorics,Search algorithm,Finite set,Computer science,Random walk,Markov chain,Variable-order Markov model,Hitting time,State space | Conference |
ISBN | Citations | PageRank |
3-642-13181-6 | 0 | 0.34 |
References | Authors | |
1 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Miklos Santha | 1 | 728 | 92.42 |