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.

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

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|cite|improve this question
No (probability) here. – Did Jan 30 '12 at 18:35

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|cite|improve this answer

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.