Roberts, Gareth O.; Rosenthal, Jeffrey S. Combinatorial identities associated with CFTP. (English) Zbl 1092.60028 Far East J. Math. Sci. (FJMS) 13, No. 3, 391-404 (2004). Summary: 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 \(C_{ab}(s)\) for different \(a\) and \(b\), where \(C_{ab}(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\). MSC: 60J10 Markov chains (discrete-time Markov processes on discrete state spaces) 05A19 Combinatorial identities, bijective combinatorics Keywords:coupling from the past; Markov chain; Markov chain Monte Carlo; combinatorial identities PDFBibTeX XMLCite \textit{G. O. Roberts} and \textit{J. S. Rosenthal}, Far East J. Math. Sci. (FJMS) 13, No. 3, 391--404 (2004; Zbl 1092.60028)