1
$\begingroup$

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?

  • 0
    No (probability) here.2012-01-30

1 Answers 1

2

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.