# What is $f(t)=X_{t+1}$, if $X_{t+1}=(1-p)(1-X_{t})+pX_{t}$ and $X_{0},p \in [0,1]$?

What is $f(t)=X_{t+1}$, if $X_{t+1}=(1-p)(1-X_{t})+pX_{t}$ and $X_{0},p \in [0,1]$?

And what are general methods for finding functions defined by such recurrent equations?

-
I'm not sure that the ~s were for, so I got rid of them. Also, it's probably better to use *words* to get italics, rather than math mode. I thought it looked kind of funky so I put it in a block quote. – Dylan Moreland Jul 20 '12 at 23:14

I will assume that $t$ ranges over, say, the non-negative integers.

For your particular example, we have \begin{align*}X_{t+2}&=(1-p)(1-X_{t+1})+pX_{t+1},\\ X_{t+1}&=(1-p)(1-X_t)+pX_t.\end{align*}

Subtract and simplify. We get $$X_{t+2}-X_{t+1}=(2p-1)(X_{t+1}-X_t).$$ So if $Y_t=X_{t+1}-X_t$, we find that $Y_{t+1}=(2p-1)Y_t$, which is easily solved, and therefore $X_t$ is $X_0$ plus the sum of a geometric series.

Remark: There are a number of good general methods for solving linear recurrences with constant coefficients. The generating functions approach is quite useful. Or else in our case we can rewrite our recurrence as $$X_{t+1}=(2p-1)X_t + 1-p.$$ First find a general solution of the homogeneous recurrence $X_{t+1}=(2p-1)X_t$. This is easy. Then find a particular solution of our non-homogeneous recurrence. Easy, by guessing that a constant might work. Then the general solution of our recurrence is the general solution of the homogeneous recurrence, plus our particular solution.

-
@TMM: Thank you, fixed. Someday I may write a typo-free answer. – André Nicolas Jul 20 '12 at 23:30
Surely with your 80k worth of contributions to this site, you will be forgiven for the occasional typo :) – TMM Jul 20 '12 at 23:32

Well, you have $X_{t+1}$ equal to a weighted average between $X_{t}$ and $1 - X_{t}$. So there's a fixed point where these are equal, i.e., at $X=1/2$. To find the behavior away from that fixed point, define $Y_{t} = X_{t} - 1/2$: then $$\begin{eqnarray} Y_{t+1}&=&X_{t+1}-\frac{1}{2} \\ &=& \left(1-p\right)\left(1 - X_{t}\right) + pX_{t} - \frac{1}{2}\\ &=& \left(1 - p\right)\left(\frac{1}{2} - Y_t\right) + p\left(Y_{t} + \frac{1}{2}\right) -\frac{1}{2}\\ &=& (2p-1)Y_{t}. \end{eqnarray}$$ So $Y_{t}$ is multiplied by a constant at each step, giving $$X_{t} = Y_{t} + \frac{1}{2} = \left(2p-1\right)^{t} Y_{0} + \frac{1}{2} = \left(2p-1\right)^{t} \left(X_{0} - \frac{1}{2}\right) + \frac{1}{2}.$$

-