Pith. sign in

REVIEW 1 cited by

The birthday problem and Markov chain Monte Carlo

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv math/0701390 v1 pith:IF7373AD submitted 2007-01-14 math.PR math.CO

Itai Benjamini , Ben Morris This is my paper · ORCID
classification math.PRmath.CO
keywords chaintimealgorithmexpectedmarkovproblemsqrtapproximation
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

We study the problem of generating a sample from the stationary distribution of a Markov chain, given a method to simulate the chain. We give an approximation algorithm for the case of a random walk on a regular graph with n vertices that runs in expected time O^*(\sqrt{n} x L^2-mixing time). This is close to the best possible, since \sqrt{n} is a lower bound on the worst-case expected running time of any algorithm.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Counting birthday collisions using partitions

    math.CO 2019-06 unverdicted novelty 3.0 of 10

    Gives partition-based formulae for counting s-collisions and related events in the birthday problem.

Pith tools