Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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'm trying to find the distribution of the second sequence after some time (say $t=10$).

I have that sequence $A$ starts at $100$ and so does sequence $B$.

If sequence $A$ moves from some value $\alpha$ to $\alpha \pm 1$, then state B will move from state $\beta$ to state $\beta \pm \frac{3\beta}{\alpha}$. How would I go about trying to get the distribution?

Edit for clarification, (and I forgot to mention this before), If $\alpha$ hits $0$, the walk is stopped.

Edit 2: As an example question, what is the probability that at time $t=10$, $B$ is greater than $100$?

share|cite|improve this question
What makes you think this should have a nice expression? – Did Nov 28 '12 at 19:50
@did, it doesn't need to be nice, say that time $t$ goes to infinity, then obviously, since the walk is random, $A$ is expected to be "near" $100$ and my question simply is... where is $B$ expected to be? and whether there is some easy way to calculate that. – picakhu Nov 28 '12 at 19:54
This is an entirely different question (and no, A is not expected to be near 100). – Did Nov 28 '12 at 20:39
@did, that was the intuition behind the actual question. The actual question is as posted (especially edit 2) – picakhu Nov 28 '12 at 21:15
Hi, I would like to ask for a clarification: say $a^{t+1}=a^t+1$. Then $\beta^{t+1}=\beta^t + \frac{3\beta^t}{a^t}$? Or the direction of the movement of $\beta$ is independent and could be e.g. $\beta^{t+1}=\beta^t- \frac{3\beta^t}{a^t}$ – user50600 Dec 3 '12 at 23:16
up vote 2 down vote accepted

You have i.i.d. random variables $\xi_1,\xi_{2},\xi_{3},\ldots$ that take on values $\pm 1$, in terms of which $$ \alpha_{n}=\alpha_{n-1}+\xi_{n} $$ and $$ \beta_{n}=\beta_{n-1}\left(1 + \frac{3\xi_{n}}{\alpha_{n-1}}\right).$$ Solving yields $$ \alpha_{n}=\alpha_{0}+\sum_{i=1}^{n}\xi_{i} $$ and $$ \beta_{n}=\beta_{0}\prod_{i=1}^{n}\left(1+\frac{3\xi_{i}}{\alpha_{i-1}}\right)=\beta_{0}\prod_{i=1}^{n}\left(1+\frac{3\xi_{i}}{\alpha_{0}+\sum_{j=1}^{i-1}\xi_{j}}\right). $$ We can write the law for $\log\beta_{n}$ as a power series expansion in $\alpha_{0}^{-1}$, which we expect to be a good approximation for $n \ll \alpha_{0}$. The first few terms are: $$ \begin{eqnarray} \log\beta_{n}&=&\log\beta_{0}+\sum_{i=1}^{n}\log\left(1+\frac{3\xi_{i}}{\alpha_{0}+\sum_{j=1}^{i-1}\xi_{j}}\right) \\ &=& \log\beta_{0}+\sum_{i=1}^{n}\left(\frac{3\xi_{i}}{\alpha_{0}+\sum_{j=1}^{i-1}\xi_{j}}-\frac{1}{2}\left(\frac{3\xi_{i}}{\alpha_{0}+\sum_{j=1}^{i-1}\xi_{j}}\right)^{2}+...\right) \\ &=&\log\beta_{0}+\alpha_{0}^{-1}\sum_{i=1}^{n}3\xi_{n}-\alpha_{0}^{-2}\left(\sum_{j<i\le n}3\xi_{i}\xi_{j} + \frac{1}{2}\sum_{i=1}^{n} 9\xi_{i}^{2}\right)+O(\alpha_{0}^{-3}) \\ &=&\log\beta_{0}+3\alpha_{0}^{-1}(\alpha_{n}-\alpha_{0})-\alpha_{0}^{-2}\left(\frac{3}{2}(\alpha_{n}-\alpha_{0})^{2}+3n \right)+O(\alpha_{0}^{-3}). \end{eqnarray} $$ The first-order term is a symmetric random walk, and the second-order term is a negative drift, suggesting that $\beta$ is more likely to decrease over time.

In this approximation, and assuming $n \ll \alpha_{0}$, we find that $\beta_{n} < \beta_{0}$ whenever $\alpha_{n} \leq \alpha_{0}$. So for odd $n$, $\beta_{n} < \beta_{0}$ with probability $1/2$, while for even $n$, $\beta_{n} < \beta_{0}$ with probability $1/2 + {n\choose{n/2}}2^{-(n+1)}$. For instance, this gives a decrease with probability $0.623046875$ for $n=10$. Testing this numerically, I found a decrease in $622477$ of $10^6$ trials for $\alpha_{0}=100$ and $n=10$, which is consistent with the approximation.

share|cite|improve this answer
this is very helpful! Is there a way to use this to answer the question in Edit 2? (even if there is not, just the knowledge that $\beta$ "decreases" over time is good information.) – picakhu Dec 6 '12 at 19:29
@picakhu: Yes, see the edited answer. – mjqxxxx Dec 6 '12 at 21:06
I don't quite see how you got that $\beta_{n} < \beta_{0}$ whenever $\alpha_{n} \leq \alpha_{0}$. – picakhu Dec 6 '12 at 22:17
@picakhu: If you examine the sign of the quadratic approximation for $\log\beta_{n} - \log\beta_{0}$, you find a decrease for large $\alpha_{n}$ (which isn't meaningful, since we're assuming small $n$) and for $\alpha_{n}-\alpha_{0} < n/\alpha_{0}$. In the range we're working in, $n/\alpha_{0}$ is between $0$ and $1$, so since $\alpha_{n}$ is an integer, it just has to be $\le 0$. – mjqxxxx Dec 6 '12 at 22:27
That makes a lot of sense, thanks! – picakhu Dec 6 '12 at 22:32

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.