Statistics of a simple Markov chain - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T10:16:00Z http://mathoverflow.net/feeds/question/49979 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/49979/statistics-of-a-simple-markov-chain Statistics of a simple Markov chain Chris Taylor 2010-12-20T17:16:59Z 2010-12-20T22:34:21Z <p>Imagine a two-state Markov chain which hops between the states $\pm 1$ with probability $p&lt;1/2$, so that the autocorrelation function after $k$ steps is</p> <p>$\rho_k = (2p-1)^k$</p> <p>If I take an exponential moving average of this series with weighting parameter $\lambda$, what does the distribution of values of the new series look like?</p> <p>Probably the answer is "gaussian, centered on 0" but what is the variance? Is there a known result that makes this computation trivial?</p> http://mathoverflow.net/questions/49979/statistics-of-a-simple-markov-chain/50001#50001 Answer by maxdev for Statistics of a simple Markov chain maxdev 2010-12-20T21:46:04Z 2010-12-20T21:46:04Z <p>By exponential moving average you mean something like $b_k = C \sum_{i=k}^{\infty} {\frac{a_i}{\lambda^i}}$ ? If $\lambda$ is small enough then this would depend hugely on $a_k$ and so it wouldn't be gaussian right?</p> http://mathoverflow.net/questions/49979/statistics-of-a-simple-markov-chain/50002#50002 Answer by Didier Piau for Statistics of a simple Markov chain Didier Piau 2010-12-20T21:59:09Z 2010-12-20T22:20:40Z <p>The answer is certainly not "Gaussian". What you describe is often called Bernoulli convolutions and, even in the independent case (in your setting, $p=1/2$), the limiting object is quite complicated and interesting since it involves some deep number theoretic properties of $\lambda$.</p> <p>To begin with, let $(X_n)_{n\in \mathbb{Z}}$ denote the $\pm1$-valued Markov chain with probability $p$ of switching states. Let $(Y_n)_{n\in \mathbb{Z}}$ denote the exponential moving average of parameter $\lambda$ with $0&lt;\lambda &lt; 1$ you are interested in, that is, $$Y_n=\sum_{k=0}^{+\infty}\lambda(1-\lambda)^kX_{n-k}.$$ The Markov chain is centered and has correlation $E(X_nX_{n+k})=(1-2p)^k$ for every integers $n$ and $k\ge0$. (Hence you should check your formula.) From there, one sees that $Y_n$ is centered and one can compute its variance. If I am not mistaken, one finds something like $$E(Y_n^2)=\frac{1-2p(1-\lambda)/(2-\lambda)}{1+2p(1-\lambda)/\lambda}.$$ The stationary distribution of the moving average is a different story. It is often best described as a measure-valued fixed point problem, as follows. First, $Y_n=X_nY_+$ where $Y_+$ and $X_n$ are independent, and $Y_+$ is distributed like $Y_n$ conditioned on $[X_n=+1]$. Second, $Y_+$ is distributed like $\lambda+(1-\lambda)ZY_+$, where $Z=\pm1$, $P(Z=+1)=1-p$, $P(Z=-1)=p$, and $Z$ independent of $Y_+$.</p> <p>This indirect description of the stationary distribution is often the most useful tool to get some information on it.</p> <p>As regards your original "Gaussian" hint, note that conditioning on $(X_{n-k})_{0\le k\le N-1}$ for a given $N$ yields that $Y_n$ is in one of $2^N$ intervals of length $2(1-\lambda)^N$. If $2(1-\lambda)&lt;1$, this simple remark shows that the distribution of $Y_n$ is concentrated on a Cantor set of Lebesgue measure zero (hence this probability distribution does not even have a density with respect to the Lebesgue measure, and it has no atom either). The argument uses only the fact that each $X_n=\pm1$ almost surely and not the structure of the process $(X_n)_n$.</p> <p>Another easy case is when $\lambda=1/2$. Then, if $(X_n)_n$ is in fact independent ($p=1/2$), one recognises the usual binary expansion of a random number hence $Y_n$ is uniformly distributed on $[-1,1]$, but for every other value of $p$, the distribution of $Y_n$ is concentrated on a subset of $[-1,1]$ of Lebesgue measure zero.</p> <p>For much more on the stationary distributions of moving averages like the ones which interests you, some starting points could be the paper <i>Sixty years of Bernoulli convolutions</i> by Peres, Schlag and Solomyak, and the book <i>Some random series of functions</i> by Kahane.</p> http://mathoverflow.net/questions/49979/statistics-of-a-simple-markov-chain/50007#50007 Answer by Nikita Sidorov for Statistics of a simple Markov chain Nikita Sidorov 2010-12-20T22:34:21Z 2010-12-20T22:34:21Z <p>The measure $\mu_\lambda$ on an interval whose distribution is given by the random variable $$\sum_{n=1}^\infty \epsilon_n\lambda^n,$$ where the $\epsilon_n$ assume the values 0 and 1 (or $\pm1$) independently with probabilities $(p,1-p)$ is called a <em>biased Bernoulli convolution</em>. </p> <p>If one assumes $\lambda\in(0,1/2)$, then $\mu_\lambda$ is supported by a Cantor set and is consequently singular. If $\lambda=1/2$, then it is a well known singular measure on $[0,1]$. (It is invariant and ergodic under the doubling map $\tau x=2x\ \bmod 1$ and so is the Lebesgue measure.)</p> <p>The most interesting case is $\lambda\in(1/2,1)$. Here if $p\in[1/3,2/3]$, then for a.e. $\lambda$ the measure $\mu_\lambda$ is known to be equivalent to the Lebesgue measure. If $\lambda^{-1}$ is a Pisot number, then it is singular. (Which was essentially proved by ErdÅ‘s in 1939.)This is almost all that is known about these measures. </p> <p>For more detail see, e.g., </p> <p><strong>B. Solomyak</strong>, <a href="http://www.math.washington.edu/~solomyak/PREPRINTS/mandel2.pdf" rel="nofollow">Notes on Bernoulli convolutions</a></p>