How to study the size of basins of attraction in a discrete dynamical system? - MathOverflow

How to study the size of basins of attraction in a discrete dynamical system?

2011-05-06T14:57:35Z

I have a discrete dynamical system in $[0,1]^n$. Specifically, I am studying the dynamics of a probability distribution under certain operator $\phi$ such that $\mathbf{q}[t+1]=\phi(\mathbf{q}[t])$. The probability distribution is specified by $n$ parameters in the $n$-dimensional vector $\mathbf{q}$. What I need to know is whether a specific starting point $\mathbf{q}_0$ is in the basin of attraction of another specific point $\mathbf{q}'$. The only way that I have to check this is by running a computer program. I would like to know how to analyze mathematically this type of global behaviors of the system. More in general, studying the size of the basin of attraction of the point $\mathbf{q}'$ would be very important. What type of mathematical tools are needed to study this kind of issues?

Thanks in advance!

Answer by Abdelmalek Abdesselam for How to study the size of basins of attraction in a discrete dynamical system?

2011-05-06T17:13:05Z

I don't think there is a magic theorem here which works all the time. What you want depends a lot on the specific $\phi$, ${\bf q}'$, ${\bf q}_0$ you are working with. What you said sounds a lot like a toy model for the renormalization group, which is a way to study central limit type theorems. For instance the classical central limit theorem can be interpreted as a convergence in the basin of attraction of the Gaussian $\mathcal{N}(0,1)$ law with respect to a map $\phi$ on probability distributions of centered variables with variance 1 given by $$ Z\longrightarrow \frac{X+Y}{\sqrt{2}}\ . $$ Namely given a probability distribution for a random variable $Z$, one makes two independent copies $X$, $Y$, and looks at the probability distribution of $\frac{X+Y}{\sqrt{2}}$.

In the absence of a precise description of your setup I can only throw in some general ideas. The first thing to do is to identify the fixed points of your map $\phi$. I assume it is nonlinear, so this is not a trivial question. If you cannot solve it completely, you need to at least find some easy fixed points. I assume this is what your ${\bf q}'$ is. Then you need to analyze the linearization of $\phi$ at these easy fixed points. I am again assuming that you did that and found that this linearization $A$ has all eigenvalues of modulus less than 1 so it is contractive. From this it follows easily that if you start near ${\bf q}'$ you will converge to ${\bf q}'$. If your starting point ${\bf q}_0$ is not in this neighborhood of ${\bf q}'$, then indeed you might want to run some simulations on the computer not only for ${\bf q}_0$ but also for many other starting points. In the optimistic situation where the simulation indicates that all points go to ${\bf q}'$, then there could be a Lyapunov function for your map, see http://en.wikipedia.org/wiki/Lyapunov_function That's a function which changes monotonically under $\phi$. If you have such a function which controls the norm of ${\bf q}$ then it might tell you that after enough iterations you will be in the neighborhood of ${\bf q}'$ where you have the contraction property. Of course the difficult thing is to come up with the correct guess for this Lyapunov function if it exists. This guess depends on the specifics of your example. For the central limit theorem there is a notion of entropy which does the job.

Some references:

the book "Information theory and the central limit theorem" by Oliver Johnson, Imperial College Press, 2004.
the book "Theory of probability and random processes" by Koralov and Sinai which mentions the renormalization group approach to the CLT.
you may also find more ideas in the paper by Takashi, Tetsuya and Watanabe "Triviality of hierarchical Ising model in four dimensions" Comm. Math. Phys. 220 (2001), no. 1, 13–40. A preprint version is available at http://www.ma.utexas.edu/mp_arc-bin/mpa?yn=00-397

Answer by Pait for How to study the size of basins of attraction in a discrete dynamical system?

2011-05-06T18:48:01Z

Recipe: Find an equilibrium point. Linearize the dynamical system around it. Find a quadratic Lyapunov function for the linearized system. Compute its rate of change along the trajectories of the original nonlinear system. A compact region where the rate of change is negative is inside the basin of attraction of the equilibrium point.

Many things can go wrong. Maybe the linearization is not asymptotically stable. Maybe it is, but the basin of attraction computed is too small to be useful. Then you need to search for Lyapunov functions that are not quadratic. That is a harder task, and doesn't lend itself to simple recipes as above. But is is a beginning. This is called "Lyapunov's indirect method" to study stability, because it is based on linearization. It is described in many dynamical systems and nonlinear controls textbooks.