Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The following question arises from research that I am doing in swarm intelligence. The relationships given come from geometric considerations which, I believe, should not be relevant for this problem. However, if anyone deems it necessary, I would be happy to provide more information.

I have studied this problem using numerical simulations, and what I am after now are leads on how I can attack this problem formally, or re-formulate it such that it becomes more manageable, etc. I am not a mathematician, so apologies in advance for any shortcomings in formulation and/or notation; any sort of suggestion to improve the problem would be very welcome and appreciated.

Firstly, we define the following two piecewise functions, where $R$ and $r$ are constants, and $R>r$:

$\delta(*) = \begin{cases} 0 & \text{if $(*)<R-r$}\\ \sqrt{\frac{R}{r}((*)^2 - (R-r)^2)} & \text{if $R-r\leq(*)\leq R+r$} \\ \frac{2Rr}{\sqrt{(*)^2 - (R^2+2Rr)}} & \text{if $(*) > R+r$}\end{cases}$

$f(*)=\begin{cases} (*) & \text{if $(*)<R-r$} \\ R-r & \text{if $R-r\leq(*)\leq R+r$} \\ \sqrt{(*)^2-4Rr} & \text{if $(*) > R+r$}\end{cases}$

Now, consider an large number of points $(x,y)$, initially all occupying the same point in the $xy$-plane, $(x_0, y_0)$. The points transform themselves in epochs, as follows. At the beginning of an epoch, a random 'coin toss' decides whether the points will be $x$-updated or $y$-updated.

For an $x$-update, each point undergoes the following transformation:

$y \leftarrow y + \zeta \delta(x)\\ x \leftarrow f(x)$

where $\zeta$ is a random number between $-1$ and $1$ generated differently for each point (with a uniform distribution). A $y$-update is the inverse of what is described above:

$x \leftarrow x + \zeta \delta(y)\\ y \leftarrow f(y)$

What is happening is that, after each epoch, the points are forming a new distribution in the $xy$-plane. This distribution becomes continuous if the number of points is allowed to tend towards infinity.

From numerical results, it turns out that this process has a single distribution that is a stable attractor for any initial condition $(x_0, y_0)$. After many epochs, the distribution tends towards two lines: one line is horizontal, located at $y=R-r$, and ranges from $x = 0$ to $x = R-r$. The other line is vertical, located at $x=R-r$, and ranges from $y=0$ to $y=R-r$.

share|cite|improve this question
Once in the region $x\leqslant R-r$, $y\leqslant R-r$, the dynamics is frozen, isn't it? Thus, starting from any point in the square $(0,R-r)\times(0,R-r)$, one will not accumulate on the two segments you described. Or, are you restricting the starting points to a sub-domain? – Did Apr 1 '13 at 15:25
One can believe that starting from outside of the square, the limiting distribution is concentrated on the two segments you say, but not that it does not depend on the starting point/distribution. Are you sure about this last aspect? – Did Apr 1 '13 at 15:43
@Did. Thanks for your comments. I always start it from $x,y>R+r$, because that makes more sense in my system. You may be right about starting from other regions, especially $<R-r$. In fact, you should never end up in that region unless you start inside it. That region is not of interest to me - maybe it can go altogether actually, I just put it there for completeness. – MGA Apr 2 '13 at 0:42

Some intuition

There are many ways to approach to this, here is some intuition that may help you whatever approach you follow:

Both of your functions transition functions $\delta(*)$ and $f(*)$ have the same "bins" (you already know this); these are:

  1. $(*) < R -r$
  2. $R-r<(*) < R -r$
  3. $(*) > R -r $

Also, $\delta(*)$ is bounded. Let $(*)>R+r$ (our third "bin"), then we have:

$$\delta(*) = \frac{2Rr}{\sqrt{(*)^2 - (R^2+2Rr)}} < \frac{2Rr}{\sqrt{(R+r)^2 - (R^2+2Rr)}} = \frac{2Rr}{r} = 2R$$

From here it is easy to show that $sup \{\delta(*)\} = 2R$

Lastly, $f(*)$ is decreasing on the third "bin":

$$\sqrt{(*)^2-4Rr} < (*)$$

From there, it is intuitive to think that any coordinate in the 3rd bin, will eventually decrease to the second bin since when it grows, it never grows more than $2R$ and $f(*)$ will eventually make it less than $R+r$

A vague sketch of a proof

There are multiple ways of solving this problem, here is a sketch that is kind of long but doesn't require more advanced concepts, since you are asking for some hints rather than a full proof.

Define nine states:

  1. $x$ in 1st bin and $y$ in 1st bin
  2. $x$ in 1st bin and $y$ in 2nd bin
  3. $x$ in 1st bin and $y$ in 3rd bin
  4. $x$ in 2nd bin and $y$ in 1st bin
  5. so on,
  6. ...
  7. ...
  8. ...
  9. $x$ in 3rd bin and $y$ in 3rd bin

Let say that the $ith$ iteration is on 'State 9' (this the most interesting one). It means that:

$$x_i > R-r \ \ \ \ \ and \ \ \ \ \ y_i > R-r$$

Imagine that a sequence of $n$ epochs with x-update happen, then:

$x_{i+1}=f(x_i) > x_{i}$ and eventually $x_{i'} \leq R-r$ for some $i'$

and that point will be outside of the 9th state. This can be stated as: $$P(x_n > R+r, y_n > R+r) \rightarrow 0$$

Similar arguments hold for the 3rd and the 6th bins. If you apply limits to all the states, you will see that only the 2nd and the 4th bin will have a non-zero limit probability (recurrent states, in more precise terminology). That's why get the limit state lies on the lines $y=R-r$ and $x=R-r$. They are line segments with length $R-r$ because there is a random walk in the coordinate that stays in the 1st bin, and randomly will lay between $0$ and $R-r$.

share|cite|improve this answer
At this level of vagueness it is difficult to see something actually proved. In any case the argument which leads to "Hence the sequence will go out of the 9th bin" is squarely wrong since it would show that every (biased) random walk on the real line hits 0 with full probability (a result which is not true). – Did Apr 3 '13 at 5:17
@Did, you are right, I had a typo in the "bin" description, it was $R-r$ instead of $R-R$. I will edit the answer to remove some vagueness. – papirrin Apr 3 '13 at 8:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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