Exact calculation of pattern probabilities
Jayadev Acharya, Hirakendu Das, Hosein Mohimani, Alon Orlitsky, Shengjun Pan · 2010
We describe two algorithms for calculating the probability of m-symbol length-n patterns over k-element distributions, a partition-based algorithm with complexity roughly 2O(m log m)and a recursive algorithm with complexity roughly 2O(m+log n)with the precise bounds provided in the text. The problem is related to symmetric-polynomial evaluation, and the analysis reveals a connection to the number of connected graphs.