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

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?

-

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:

-
Thank you so much for your time. Your suggestions and references are really useful for me. I know some easy fixed points of the system. For example, I know that the points $\{0,1\}^n$ are fixed points. In addition, I also can identify some attractive fixed points such as $\mathbf{q}'$. In essence, the systems are formed by products among the parameters $q_i \in \mathbf{q}$ and summations. I am not sure if this is relevant. In any case I have to study Lyapunov functions. –  Navcar May 6 '11 at 19:27

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.

-
Thank you for the recipe! It contains a lot of information in few words. Certainly, I need to think carefully about this. –  Navcar May 6 '11 at 19:49
The long version appears in many control theory texts. Let me know if you'd like pointers. –  Pait May 8 '11 at 22:49
I do not know if it could be possible to find a reference with a simple example of the procedure that you describe. Thanks! –  Navcar May 12 '11 at 13:14