×

Combinatorial identities associated with CFTP. (English) Zbl 1092.60028

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
PDFBibTeX XMLCite