Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider a point on the $xy$-plane whose position is updated in iterations. In each iteration, the point undergoes, with equal probability, either an $A$- or a $B$-update, defined as follows:

$A$-update: $\cases{x_{i+1} = \sqrt{x_i^2-k}\\ y_{i+1} = y_i + \delta(x_i) \\ },\qquad$ $B$-update: $\cases{x_{i+1} = x_i + \delta(y_i) \\ y_{i+1} = \sqrt{y_i^2-k}},$

where $\delta(\cdot) = \frac{\alpha}{\sqrt{(\cdot)^2 - \beta}}$, $k,\alpha> 0$, and $0\leq \beta \leq k.$

The sequence terminates when either $x_i$ or $y_i$ $\leq \sqrt{k+1}$.

The dynamics are interesting because, in an $A$-update, $x$ decreases while $y$ increases, and $y$ increases more as $x$ gets smaller (and vice-versa for a $B$-update).

Questions:

  • For which values of $k$, $\alpha$ and $\beta$ is the sequence guaranteed to terminate after a finite number of iterations?

  • How many iterations does it take for the sequence to terminate in the worst case scenario, given $x_0$ and $y_0$?

PS: I had asked an earlier version of this question, which was too convoluted, and remained without a satisfactory answer. I have presented a much simplified version here.

share|improve this question
    
A couple of observations I have made so far: (i) for any $k$, $\alpha$, and $\beta$, the sequence may terminate, if it undergoes a consecutive number of either $x$- or $y$-updates. (ii) The least possible number of iterations for the sequence to terminate is when an unbroken string of either $x$- or $y$-updates occurs, depending on which of $x_0$ and $y_0$ is the smaller. In this case, the number of iterations can be easily calculated. –  MGA Apr 8 '13 at 4:13
    
If there is a non-zero probability that the sequence may terminate than the sequence must terminate given infinite steps unless it can enter a state where that probability drops to zero. –  Dale M Apr 9 '13 at 1:46
    
@Dale M Thanks, that's a good observation - I have not phrased the question well enough. What I'm looking for is a guarantee that the sequence terminates after at most some number of steps whatever the sequence of updates is. Does that make it more clear? –  MGA Apr 9 '13 at 2:03
    
For the functions with $\delta$, $z_{i+1}\gt z_{i}$ always but for the others $z_{i+1}\lt z_{i}$ only when $z_{i}^2-k\ge1$ i.e. $z_{i}\ge\sqrt{k+1}$ –  Dale M Apr 9 '13 at 2:40
    
@DaleM That's right. That's why the sequence terminates when either $x_i$ or $y_i$ $<\sqrt{k+1}$ (it was mistakenly $\sqrt{k}$, I have edited it to correct it). –  MGA Apr 9 '13 at 3:09

1 Answer 1

up vote 1 down vote accepted

For the process to terminate in a finite number of steps, say $N$, at step $N-1$ it must be certain that it will do so irrespective of the update. So

$$\sqrt{x_{N-1}^2-k}\le\sqrt{k+1}\text{ and }\sqrt{y_{N-1}^2-k}\le\sqrt{k+1}$$

or (knowing that all square roots are positive)

$$\sqrt{k+1}\lt x_{N-1},y_{N-1}\le\sqrt{2k+1}$$

At $N-2$

$$\begin{align} \sqrt{k+1}&\lt x_{N-1}=\sqrt{x_{N-2}^2-k}&\le\sqrt{2k}\\ \sqrt{2k+1}&\lt x_{N-2}\le\sqrt{3k+1} \end{align}$$

and

$$\begin{align} \sqrt{k+1}&\lt y_{N-1}=y_{N-2}+\frac{\alpha}{\sqrt{x_{N-2}^2-\beta}}\le\sqrt{2k+1}\\ \sqrt{k+1}-\frac{\alpha}{\sqrt{x_{N-2}^2-\beta}}&\lt y_{N-2}\le\sqrt{2k+1}-\frac{\alpha}{\sqrt{x_{N-2}^2-\beta}}\\ \end{align}$$

By symmetry, this must also be true if the other option was selected. So since we know that the $\alpha$ term is positive, it is clear that the lower limit is defined by the first equation and the upper limit by the second, giving

$$\begin{align} \sqrt{2k+1}&\lt x_{N-2},y_{N-2}\le\sqrt{2k+1}-\frac{\alpha}{\sqrt{x_{N-2}^2-\beta}}\\ \end{align}$$

This inequality cannot be satisfied given the constraints.

Unless I have made a mistake it is not certain that the function will terminate in a finite number of steps.

That said, it is quite likely that it will.

share|improve this answer
    
Thanks, that's some useful insight. I'll keep working on it and will accept your answer soon if it's still the best one available. –  MGA Apr 9 '13 at 9:28
    
Some ideas: can you state (or modify) your model as a function of complex variables - this may open up some simpler algebra. Do you lose generality by doing so? –  Dale M Apr 10 '13 at 0:04

Your Answer

 
discard

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.