Sharp approximation for density dependent Markov chains

Details Sharp approximation for density dependent Markov chains Sharp approximation for density dependent Markov chains

2009-08-14

arxiv.org/abs/0908.2088v1

Mathematics

Probability

Scientific paper

Consider a sequence (indexed by n) of Markov chains Z^n in R^d characterized by transition kernels that approximately (in n) depend only on the rescaled state n^{-1} Z^n. Subject to a smoothness condition, such a family can be closely coupled on short time intervals to a Brownian motion with quadratic drift. This construction is used to determine the first two terms in the asymptotic (in n) expansion of the probability that the rescaled chain exits a convex polytope. The constant term and the first correction of size n^{-1/6} admit sharp characterization by solutions to associated differential equations and an absolute constant. The error is smaller than O(n^{-b}) for any b < 1/4. These results are directly applied to the analysis of randomized algorithms at phase transitions. In particular, the `peeling' algorithm in large random hypergraphs, or equivalently the iterative decoding scheme for low-density parity-check codes over the binary erasure channel is studied to determine the finite size scaling behavior for irregular hypergraph ensembles.

Affiliated with

Also associated with

No associations

Rating

Sharp approximation for density dependent Markov chains does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sharp approximation for density dependent Markov chains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sharp approximation for density dependent Markov chains will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-272637