Local extrema of a posterior probability

Question

Let $x$ be a binary random variable and $z$ be an arbitrary random variable. $x$ and $z$ are, in general, not independent.

Let $y_1, \ldots y_n$ be $n$ identically distributed binary random variables conditionally independent given $z$.

A graphical model would have $x$ at the root, pointing to $z$, and $z$ pointing to each of the $y_i$.

Consider random variable $c = \sum y_i$ and function $f(k) = p(x=1|c=k)$ defined from $k=0$ to $n$.

How many local extrema can $f$ have, at most? That is, points where $(f(k)-f(k-1))(f(k+1)-f(k)) < 0$

Answer 1

I think you can get as many as you like. Let X be 0 or 1 with probability 1/2 each. Let $Z|X=I$ be of the form $h \pm \epsilon q$ where q is arbitrary and can be positive or negative, and I write them as if they have a density but any measure/signed measure will, subject to the sum being a measure. First I claim that $$P(X=1| Y=k ) = \frac 12 \frac{\int x^k(1-x)^{N-k}(h(x) + \epsilon q(x)) dx)}{\int x^k(1-x)^{N-k}(h(x) dx}$$

$$ = \frac 12 + \frac{\int x^k(1-x)^{N-k} \epsilon q(x) dx)}{\int x^k(1-x)^{N-k}(h(x) dx}$$

Second, any f(k) can be written $\int x^k(1-x)^{N-k} q(x) dx$ for some measure q. Because, taking q to be a pointmass and you get a term like $\lambda^k$, and most choices of $\lambda_1,..., \lambda_N$ will give you a basis for sequences of length N. Choose a q that makes it 1,-1,1, -1 etc. Choose $\epsilon$ really small, so that $h \pm \epsilon q$ is a measure, but h is still more or less arbitrary. Choose h so that the denominator varies much slower than the numerator, and you ought to get $P(x=1|y=k)$ being alternately a little bigger that 1/2 and a little less than 1/2.

Proposer asks: can you be more explicit etc. Let me illustrate in the simplest case, N=1. I'm going to put mass a at 1/2 and b 3/4. Then I have 2 equations in 2 unknowns, which come from specializing $$ f(k) = \int p^k(1-p)^{N-k} dq(p) $$ in the case N=1 to $$ f(0) = -1 = \frac 12 a + \frac 14 b $$ and $$ f(1) = 1 = \frac 12 a + \frac 34 b$$. It has a solution, which is a $\it{signed}$ measure. In general you'd just want to observe that the system of equations has a solution.