Take the 2-minute tour ×

A pair of positive integers $x_0$ and $y_0$ are selected and further pairs are generated according to the following rule:

After the values of $x_n$ and $y_n$ have been found, a coin is tossed. If it lands heads, then $x_{n+1} = x_n −1$ and $y_{n+1} = x_n$. Otherwise, if it lands tails, then $x_{n+1} = y_n − 2$ and $y_{n+1} = x_n + 1$.

The process ends when a non-positive value of $x$ or $y$ is generated. Is there a choice of initial values for $x_0$ and $y_0$ and sequence of coin toss outcomes for which the sequence of $x$’s and $y$’s does not terminate?

share|improve this question
By the "Q2" in the original post, and the lack of motivation I have added the [homework] tag, if this is not actually a homework question feel free to remove it. –  Asaf Karagila Jan 28 '12 at 21:05
No (probability) here. –  Did Jan 30 '12 at 18:35

1 Answer 1

The process ends for every starting point and every sequence of moves.

Call $h:(x,y)\mapsto(x-1,x)$ and $t:(x,y)\mapsto(y-2,x+1)$. For every $x$, let $u_x=(x,x+1)$. Call $U$ the set of points $u_x$ and $x$ the rank of the point $u_x$.

Then $t\circ t:(x,y)\mapsto(x-1,y-1)$ hence if one uses $t$ only, the process ends. As soon as one uses $h$, the result is $h(x,y)=u_{x-1}$ hence one lands in $U$.

Now, $h(u_x)=u_{x-1}$, $t\circ t(u_x)=u_{x-1}$ and $h\circ t(u_x)=u_{x-2}$, hence, from this moment on, one stays in $U$ every one or two steps. The sequence of the ranks is decreasing hence the ranks cannot stay positive forever.

It seems that no path starting from $(x,y)$ with length at least twice the maximum of $x$ and $y$, lies entirely in the positive orthant.

share|improve this answer

Your Answer


