Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example

Details Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example

2011-10-18

arxiv.org/abs/1110.3856v2

Mathematics

Probability

31 pages

Scientific paper

Many natural simulation tasks, such as generating a partition of a large integer $n$, choosing uniformly over the $p_n$ conceivable choices, might be done by proposing a random object from a larger set, and then checking for membership in the desired target set. The success probability, i.e., the probability that a proposed random object hits the target, may be very small. The usual method of rare event simulation, the exponential shift or Cram\'er twist, is analogous to the saddle point method, and can remove the exponentially decaying part of the success probability, but even after this, the success probability may still be so small as to be an obstacle to simulation. To simulate random integer partitions of $n$, using Fristedt's method, the initial proposal is a partition of a random integer of size around $n$, so that the counts of parts of each size are mutually independent. The usual method corresponds to evaluating the generating function at $\exp(-\pi/\sqrt{6n})$, and the remaining small probability is asymptotic to $(96n^3)^{-1/4}$. Here, we propose a new method, probabilistic divide-and-conquer, for dealing with the small probability, e.g., the order $n^{-3/4}$ probability in the example of integer partitions. This method is analogous to changing a very difficult game, in which "hole in one" is the only way to score, to the usual game of golf. There are many variations on the basic idea, including a simulation technique we call mix-and-match, with features of the coupon collector's problem. For the case of integer partitions, we have a close to ideal recursive scheme, not involving mix-and-match. The asymptotic cost is $\sqrt{2}$ times the cost to propose a random partition of a random integer of size around $n$, so that the algorithm is within O(1) of the entropy lower bound.

Affiliated with

Also associated with

No associations

Rating

Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example 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 Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-289552