0
$\begingroup$

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$

$\endgroup$
6
  • $\begingroup$ what kind of answer are you looking for ? $\endgroup$
    – user83457
    Jan 15 '16 at 11:04
  • $\begingroup$ At this point, even proving asymptotic bounds would be cool. $\endgroup$
    – Arthur B
    Jan 15 '16 at 14:09
  • $\begingroup$ e.g. $o(\sqrt n)$ ? What's the worst case you've got ? $\endgroup$
    – user83457
    Jan 15 '16 at 14:12
  • $\begingroup$ For example, though I'm conjecturing at least $O(\sqrt n)$ $\endgroup$
    – Arthur B
    Jan 15 '16 at 14:13
  • $\begingroup$ I think you can get $O(n^{\alpha})$ extrema for $\alpha < 1/2$ pretty easily. $\endgroup$
    – user83457
    Jan 15 '16 at 14:15
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Can you be a bit more explicit about writing any $f(k)$ by picking the right measure $q$? $\endgroup$
    – Arthur B
    Jan 15 '16 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.