Exchangeable Hoeffding decompositions over finite sets: a characterization and counterexamples

We study Hoeffding decomposable exchangeable sequences with values in a finite set D. We provide a new combinatorial characterization of Hoeffding decomposability and use this result to show that, if the cardinality of D is strictly greater than 2, then there exists a class of neither P\'{o}lya nor i.i.d. D-valued exchangeable sequences that are Hoeffding decomposable. The construction of such sequences is based on some ideas appearing in Hill, Lane and Sudderth [1987] and answers a question left open in El-Dakkak and Peccati [2008].