3

Consider the following dynamic process. Time is discrete, indexed by $t = 0, 1, 2, \dots$. A variable $s_t$ evolves according to a fixed function $f \colon [0, 1] \rightarrow [0, 1]$; so for any time $t$, $s_{t+1} = f(s_{t})$. Finally, the initial value $s_0$ is in $[0, 1]$.

It is fairly obvious that any fixed point of the function $f$ must be a limit of this process given an appropriately chosen starting value $s_0$. To see this, take any fixed point $s^*$ and suppose that $s_0 = s^*$. Then $s_1 = f(s_0) = f(s^*) = s^*$, $s_2 = f(s_1) = f(s^*) = s^*$, and so forth; and so the state variable $s_t$ remains stuck at $s^*$ forever.

Supposing that $f$ is continuous, I also believe that every limit of this process must be a fixed point. However, how I can prove this? I believe that the continuous mapping theorem is crucial to the argument.

Although it is not my primary question, I would also be interested to learn if there is a theorem establishing that this process must have a limit (I guess this might require that $f$ is increasing to prevent cycles?) Suggested readings would also be welcome.

afreelunch
  • 643

1 Answers1

3

i) If the limit exists and $f$ is continuous: $$s^*=\lim_{t\to \infty} s_{t} = \lim_{t\to \infty} s_{t+1} = \lim_{t\to \infty} f(s_{t}) =f(\lim_{t\to \infty} s_{t}) = f(s^*)$$ so it must be a fixed point.

ii) The sequence $(s_t)_{t=1}^{\infty}$ is bounded so it always contains a converging sub-sequence.

iii) Take $f(s) = 1-s$, then with $s_0=0$ the sequence $(s_t)_{t=1}^{\infty}$ does not converge.

iv) For further readings on the topic I recommend you the book "An Introduction to Metric Spaces and Fixed Point Theory" from Khamsi and Kirk

Surb
  • 55,662
  • 1
    Thanks for the amazing answer! Two quick questions if I may: 1) can I confirm that the penultimate equality holds by the continuous mapping theorem? 2) I guess the sequence must converge if $f$ is monotone? – afreelunch Apr 21 '22 at 18:26
  • yes, 2) If $f$ is monotone, then $(s_t)_{t=1}^{\infty}$ is a monotonic bounded sequence, and therefore converges, so yes :). But there are other conditions which guarantee convergence (e.g. $f$ being a contraction, etc.).
    • – Surb Apr 21 '22 at 18:27
  • My apologies for the endless questions, but I have just realised that, as shown by your helpful example ($f(s) = 1 - s$), monotonicity of $f$ does not guarantee convergence (since the sequence $(s_t)_{t=1}^{\infty}$ can fail to be monotone). However, perhaps convergence is guaranteed by assuming that $f$ is increasing? – afreelunch Apr 25 '22 at 16:37