Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to model the following sum:

$\sum_{i=0}^{n}{W_i \alpha^{i}}$

where $\alpha \in[0, 1) $ and $W_n$ takes values 0 or 1 and may be modeled as a markow chain or for simplicity as a binary random variable with $P(W=0)=p_0$ and $P(W=1)=1-p_0$

In the special case in which $n->\infty$ and $p_0=0$ the series should converge to $1\over{1-\alpha}$ and I suppose the infinite series will converge to $(1-p_0)\over{1-\alpha}$ when $p_0 \in (0,1]$.

I would like to understand whith what probability the sum above will be greater than a given threshold depending on the threshold itself, on the properties of $W_n$, on $n$ and of $\alpha$.

Is there some relevant theory I could use to model this problem (or a simplfied version of it)?

share|cite|improve this question
You mean $\sum_{i=0}^n W_i\alpha^i$ I presume? – Siméon Jan 21 '13 at 10:35
thank you, edited. – Gianni Jan 21 '13 at 13:52
up vote 1 down vote accepted

When $n\to\infty$, the random variables $X_n=\sum\limits_{i=0}^nW_i\alpha^i$ converge almost surely to some non deterministic limit $X=\sum\limits_{i=0}^{+\infty}W_i\alpha^i$. Obviously, $0\lt X\lt x_\alpha$ with $x_\alpha=\frac1{1-\alpha}$ with full probability. The distribution of $X$ is uniquely determined by the fact that the identity in distribution $$ W'+\alpha X'\stackrel{\text{dist.}}{=}X, $$ for some independent $W'$ and $X'$ distributed as $W$ in the question and as $X$, respectively. Not everything is known about the distribution of $X$, and by far, but the following results hold:

  • In the special case $p_0=\frac12=\alpha$, the distribution of $X$ is uniform on $[0,1)$.
  • When $p_0\ne\frac12=\alpha$, the distribution of $X$ is singular and without atom, on $[0,1)$.
  • When $p_0=\frac12\gt\alpha$, the distribution of $X$ is singular and without atom, on $[0,x_\alpha)$.
  • When $p_0=\frac12\lt\alpha$, to determine whether the distribution of $X$ is singular or not is called the Erdős problem.

To learn more about this exciting subject, see the survey Iterated random functions by Diaconis and Freedman, especially Section 2.5 for the model in this post.

share|cite|improve this answer
Thank you very much for the answer and reference. In the identity you wrote do you intend $W$ is distributed as $W_0$ or as any of the samples of $W$ or did i miss something important about $W_1$? – Gianni Jan 21 '13 at 14:28
No no, as your W_0. – Did Jan 21 '13 at 14:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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