# A Coupled Random Walk on the xy-Plane

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.

-
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

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.

-
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