Counting balanced sequencesw/o forbidden patterns via the betheapproximation and loop calculus
Pascal O. Vontobel · 2014
Motivated by coding-theoretic questions that arise in the context of flash-memory-based data storage, we consider the problem of (approximately) counting the number of sequences of length n that are balanced and that avoid certain patterns. We do this by formulating a suitable factor graph whose total sum represents the desired quantity, by computing the Bethe approximation of the total sum, and by bounding the difference between the total sum and its Bethe approximation via the loop calculus technique. Although there are alternative techniques for counting the above-mentioned sequences, the presented counting technique has the potential to generalize more easily to other setups.