2
$\begingroup$

Following the probability problem

Suppose we have the sequence

$$p_1=\frac{2}{3}$$ $$p_n=\frac{2-p_{n-1}}{3}$$

Obviously if the limit exists, it is $p_\infty=1/2$

How to prove convergence?

$\endgroup$

5 Answers 5

4
$\begingroup$

Observe that $2p_n-1=\frac{1-2p_{n-1}}{3}$, from which it follows that $$ \left|p_n-\tfrac12\right|=\frac{\bigl|p_{n-1}-\tfrac12\bigr|}{3}=\frac{\bigl|p_{n-2}-\tfrac12\bigr|}{3^2}=\cdots =\frac{\bigl|p_{1}-\tfrac12\bigr|}{3^{n-1}}=\frac{1}{2\cdot 3^n}, $$ and thus the distance to $\tfrac12$ decreases exponentially fast to $0$.

$\endgroup$
1
$\begingroup$

You could show $p_n=\dfrac12-\dfrac12\left(-\dfrac13\right)^n.$

$\endgroup$
2
1
$\begingroup$

If you solve the recurrence equation $$p_n=\frac{2-p_{n-1}}{3} \qquad \text{with} \qquad p_1=a$$ you should find that $$p_n=\frac 12\left(1+(-1)^n \frac {1-2a}{3^{n-1}}\right)$$

A simple way could be : let $p_n=q_n+b$ and replace to get $$\frac{4 b-2}{3}+\frac{1}{3} q_{n-1}+q_n=0$$ and choosing $b=\frac 12$ reduces the equation to $$\frac{1}{3} q_{n-1}+q_n=0\implies q_n=c_1 \left(-\frac{1}{3}\right)^{n-1}\implies p_n=\frac 12+c_1 \left(-\frac{1}{3}\right)^{n-1}$$ and $p_1=a$ leads to $c_1=\frac{2a-1}{2} $

$\endgroup$
0
$\begingroup$

The key word here is arithmetic geometric sequence.

A sequence $\{p_n\}_{n\geqslant 1}$ is arithmetic-geometric if there exists constants $a$ and $b$ such that $p_{n+1}=ap_n+b$ for every $n \geqslant 1$.

In what follows, I will assume that $a\neq 1$ (otherwise, the sequence is simply arithmetic).

Consider the linear function $f(x)=ax+b$. Since $a\neq 1$, $f$ has a fixed point $\ell$ (that is $f(\ell)=\ell$). In the example from the OP, we have $f(x)=\frac{2-x}{3}$ and $\ell=\frac{1}{2}$.

Consider now $q_n=p_n-\ell$. Then $\{q_n\}$ is geometric of common ratio $a$ and first term $q_0=p_0-\ell$. Indeed,

$$q_{n+1}=p_{n+1}-\ell = (a p_n + b) - (a\ell + b) = a(p_n - \ell) = a q_n$$

Therefore, we have $q_n=a^{n-1}q_0$ so $p_n = a^{n-1}(p_0-\ell)+\ell$. In the example from the OP, we have $p_{n} = \frac{1}{6}\left(\frac{1}{2}\right)^n+\frac{1}{2}$.

Finally,

  • In the case where $|a|<1$, the sequence $\{p_n\}$ converges to $\ell$.
  • In the case where $|a|>1$, the sequence is divergent.
$\endgroup$
0
$\begingroup$

Let $f(x)=\frac{2-x}{3}$. Then $f'(x)=-\frac{1}{3}$ and so $|f'(x)|<1$. Therefore, $f$ is a contraction and so iterating $f$ converges to its unique fixed point, no matter what initial point you take (Banach fixed-point theorem).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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