Combinatorial identifites associated with CFTP.
Gareth O. Roberts, Jeffrey S. Rosenthal · Lancaster EPrints (Lancaster University) · 2004
We explore a method of obtaining combinatorial identities by analysing partially-completed runs of the Coupling from the Past (CFTP) algorithm. In particular, using CFTP for simple symmetric random walk (ssrw) with holding boundaries, we derive an identity involving linear combinations of Cab(s) for different a and b, where Cab(s) is the probability that unconstrained ssrw run from 0 for time n has maximum value a, and minimum value b, and ends up at s at time n.