A Band and Bound Technique for Simple Random Algorithms

A simple random algorithm (SRA) is an algorithm whose behavior is governed by a first-order Markov chain. The expected time complexity of an SRA, given its initial state, is essentially the time to absorption of the underlying chain. The standard approach in computing the expected runtime is numeric...

Full description

Saved in:
Bibliographic Details
Published in:Probability in the engineering and informational sciences 1990-07, Vol.4 (3), p.333-344
Main Author: Rego, Vernon
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A simple random algorithm (SRA) is an algorithm whose behavior is governed by a first-order Markov chain. The expected time complexity of an SRA, given its initial state, is essentially the time to absorption of the underlying chain. The standard approach in computing the expected runtime is numerical. Under certain conditions on the probability transition matrix of an SRA, bounds on its expected runtime can be obtained using simple probabilistic arguments. In particular, one can obtain upper and lower (average time) logarithmic bounds for certain algorithms based on SRAs.
ISSN:0269-9648
1469-8951
DOI:10.1017/S0269964800001649