TY - JOUR

T1 - Combinatorial identifites associated with CFTP.

AU - Roberts, Gareth O.

AU - Rosenthal, Jeffrey S.

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

KW - Coupling from the Past (CFTP)

KW - Markov chain

KW - Markov chain Monte Carlo (MCMC)

KW - combinatorial identities.

M3 - Journal article

VL - 13

SP - 391

EP - 404

JO - Far East Journal of Mathematical Sciences

JF - Far East Journal of Mathematical Sciences

SN - 0972-0871

IS - 3

ER -