9
$\begingroup$

Imagine a coin with a time-varying probability of coming up heads. (For example, perhaps the probability follows a random walk that is constrained to live in $[0, 1]$. And say we have some information about how quickly we expect the true probability to vary over time (analogous to the standard deviation of the random walk described above).

At discrete time points, we are given data about the outcome of a given coin flip. The goal is to come up with a robust procedure to estimate that probability over time.

This sounds like a task for a Kalman filter. But the literature seems to assume that the observations will be normally distributed around a linear function of the state. That feels quite violated by the assumptions above.

What's a reasonable way to proceed?

Improve this question
$\endgroup$
4
  • $\begingroup$ @RodrigodeAzevedo Could work around with log-likelihood. Can we get away with (0,1) instead? $\endgroup$
    – AHusain
    Commented Dec 7, 2016 at 23:17
  • 4
    $\begingroup$ @8none6, there is a general algorithm called sum-product (or max-product) or belief propagation, generalizing Kalman filters. See for example. What you describe sounds like a hidden markov model with a discrete observation, and you can use sum-product in this case too. $\endgroup$
    – passerby51
    Commented Dec 8, 2016 at 5:27
  • $\begingroup$ The extended Kalman filter works for any smooth (locally linear) generative model for your data, with the assumption of a gaussian and decorrelated noise. $\endgroup$
    – reuns
    Commented Dec 11, 2016 at 18:30
  • $\begingroup$ Well, as per above, we're good on the locally linear model for the hidden variable. But the whole point is to discuss a highly non-normal model for the noise on the observation process. $\endgroup$
    – 8one6
    Commented Dec 12, 2016 at 1:30

4 Answers 4

Reset to default
4
$\begingroup$

In principle, this is what nonlinear filtering does. Check this out, also under the name "hidden Markov model". Particle filters can be adapted to deal with this setup.

In a nutshell, here is what hidden Markov processes are. You have a two component Markov chain $(X_n,Y_n)$ (I write it in discrete time, there is an analogue in continuous time). You observe only $\{Y_i\}_{i=1}^n$ and want to estimate $X_n$, i.e. construct the conditional pdf of $X_n$ given the observations.

In your case, the law of $Y_n$ given the state history $\{X_i\}_{i=1}^n$ depends only on $X_n$ and is a Bernoulli variable with mean depending on $X_n$. $X_n$ itself is what you call $p$.

PS I just noted that my answer is closely related to that of @passerby51.

Improve this answer
$\endgroup$
4
  • $\begingroup$ If you can point me to a resource that explains how to use this approach to solve my problem, I'll read up so I can consider accepting this answer... $\endgroup$
    – 8one6
    Commented Dec 12, 2016 at 1:32
  • $\begingroup$ global.oup.com/academic/product/… has probably more information than you bargained for. $\endgroup$
    – ofer zeitouni
    Commented Dec 13, 2016 at 8:55
  • $\begingroup$ ...and if my bargaining skills are not at the top of their game, a higher price thanI bargained for, too! $\endgroup$
    – 8one6
    Commented Dec 14, 2016 at 11:17
  • $\begingroup$ Sure. Nobody buys these books except for select libraries. If you have no access, note that most articles are on arxiv. $\endgroup$
    – ofer zeitouni
    Commented Dec 15, 2016 at 10:52
2
$\begingroup$

The Kalman filter is based on an assumption of Gaussian noise in both the observations and process. As I read your problem statement you have no observation noise. Given that, I don't think the KF is the correct choice.

"Yes, well, I'll just set the measurement noise to zero". The problem is that the KF performs the update step in measurement space. If you have no measurement noise, then you have no uncertainty in the normal to the measurement hyperplane. The system covariance ends up being singular (the math blows up).

Off the top of the head I don't know the correct approach to your question, but this does not sound like a KF application to me.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I don't agree with the statement that I have no measurement noise. I flip a coin. At that instant, it has a true probability p of coming up heads (which I do not know). It comes up heads. That doesn't mean p=1.0. The outcome of the single coin toss should be assumed to be a draw from a probability distribution whose parameters are unknown and which we are trying to infer. $\endgroup$
    – 8one6
    Commented Dec 8, 2016 at 14:05
  • $\begingroup$ Put another way, my observations are not error-free...just they are distributed "very-non-normally" around their true value. $\endgroup$
    – 8one6
    Commented Dec 8, 2016 at 17:39
  • $\begingroup$ I see what you are saying. In your case p is a hidden variable, and you regard a flip as a probabilistically distributed observation of p. But measurement noise in a KF is the noise in the observed variable. I use a GPS to measure position, with error, then I can compute an unobserved variable, such as velocity. In your case the observed variable is the current flip, which you measure perfectly. $\endgroup$
    – Roger Labbe
    Commented Dec 9, 2016 at 15:07
  • $\begingroup$ Sorry, I hit return. In the update step you work in measurement space, which means the measurement covariance is the error in the measurement of the flip, not the error in the sampling from the state. $\endgroup$
    – Roger Labbe
    Commented Dec 9, 2016 at 15:11
  • $\begingroup$ I have no idea if the KF can be extended to your way of thinking - I work with them in Newtonian systems, where what I say very much applies. Particle filters do not require assumptions of linear systems or gaussian distributions, so if this is a fruitful line of thinking perhaps you'd be better served with one of them? $\endgroup$
    – Roger Labbe
    Commented Dec 9, 2016 at 15:13
1
$\begingroup$

What I would try when facing such a problem:

1°) Minimize $\lambda\int p'(t)^2\ dt +$ the sum of informations $\log (1/p(t_k))$ if heads at $t_k$, $\log (1/[1-p(t_k)])$ if tails.

2°) Chose $\lambda$ using (a suitable form of) cross-validation.

3°) Keep searching how people did before.

Improve this answer
$\endgroup$
1
$\begingroup$

Update: A 2019 paper on arXiv addresses this problem.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Note the title of the arXiv paper was changed to "A closed-form filter for binary time series" in version 3. $\endgroup$
    – jeq
    Commented May 5, 2023 at 15:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .