Skip to main content
MathOverflow

Return to Answer

added 2111 characters in body
Source Link
Johan Wästlund
Johan Wästlund
  • 5.5k
  • 3
  • 28
  • 35

ADDED: One might worry about whether in general, a solution obtained as indicated above is the correct one. For instance, in the example with $\alpha = 1/5$, the equation $x^2 = (x^5+1)/2$ has, apart from the three real roots, also two non-real roots, and even after finding a solution $f$ involving only the two real roots other than 1, it might not be totally obvious that there is no other real function of the form $g(n) = A_1x_1^n+\cdots+A_5x_5^n$ that satisfies the boundary conditions (this would be possible if the two non-real roots had absolute value smaller than 1).

There is a simple application of Brownian motion that shows that anything that satisfies the recursion $g(n+2) = (g(n) + g(n+5))/2$ as well as the boundary conditions, must be the correct solution. I picked this up recently from Jeff Steif (in a slightly different context), who told me he heard it from Yuval Peres twenty years ago. Here is how it goes:

Suppose that someone gives us a function $g$ that satisfies $g(-1) = g(-2) = 1$, $g(n+2) = (g(n) + g(n+5))/2$ for $n\geq 0$, and $g(n)\to 0$ as $n\to\infty$. Since such a function must have the form $A_1x_1^n+\cdots+A_5x_5^n$, it is easy to see that all the values have to be in the interval $[0,1]$ (there could not be a smallest value of $g$).

Now start a Brownian motion on the real line from the point $g(0)$, and run it until it hits either $g(-2)$ or $g(3)$. If it hit $g(3)$, continue until it hits $g(1)$ or $g(6)$, etc. In finite time, the particle will reach either $1=g(-1) = g(-2)$ or 0 (in case it went through $g(n)$ for some sequence of $n$'s tending to infinity).

It follows from basic properties of the Brownian motion that the probability that it reaches 1 before reaching zero is $g(0)$. Since the process correctly emulates the discrete random walk of steps $+3$ and $-2$, it follows that the probability that the emulated walk on the integers reaches $-1$ or $-2$ before going to infinity is also $g(0)$.

Therefore the boundary conditions uniquely specify the solution (and the argument obviously generalizes to any rational $\alpha$).

ADDED: One might worry about whether in general, a solution obtained as indicated above is the correct one. For instance, in the example with $\alpha = 1/5$, the equation $x^2 = (x^5+1)/2$ has, apart from the three real roots, also two non-real roots, and even after finding a solution $f$ involving only the two real roots other than 1, it might not be totally obvious that there is no other real function of the form $g(n) = A_1x_1^n+\cdots+A_5x_5^n$ that satisfies the boundary conditions (this would be possible if the two non-real roots had absolute value smaller than 1).

There is a simple application of Brownian motion that shows that anything that satisfies the recursion $g(n+2) = (g(n) + g(n+5))/2$ as well as the boundary conditions, must be the correct solution. I picked this up recently from Jeff Steif (in a slightly different context), who told me he heard it from Yuval Peres twenty years ago. Here is how it goes:

Suppose that someone gives us a function $g$ that satisfies $g(-1) = g(-2) = 1$, $g(n+2) = (g(n) + g(n+5))/2$ for $n\geq 0$, and $g(n)\to 0$ as $n\to\infty$. Since such a function must have the form $A_1x_1^n+\cdots+A_5x_5^n$, it is easy to see that all the values have to be in the interval $[0,1]$ (there could not be a smallest value of $g$).

Now start a Brownian motion on the real line from the point $g(0)$, and run it until it hits either $g(-2)$ or $g(3)$. If it hit $g(3)$, continue until it hits $g(1)$ or $g(6)$, etc. In finite time, the particle will reach either $1=g(-1) = g(-2)$ or 0 (in case it went through $g(n)$ for some sequence of $n$'s tending to infinity).

It follows from basic properties of the Brownian motion that the probability that it reaches 1 before reaching zero is $g(0)$. Since the process correctly emulates the discrete random walk of steps $+3$ and $-2$, it follows that the probability that the emulated walk on the integers reaches $-1$ or $-2$ before going to infinity is also $g(0)$.

Therefore the boundary conditions uniquely specify the solution (and the argument obviously generalizes to any rational $\alpha$).

Source Link
Johan Wästlund
Johan Wästlund
  • 5.5k
  • 3
  • 28
  • 35

I believe that leonbloy's comment/hint is relevant, and whenever $\alpha$ is rational, $P(\alpha)$ is algebraic. For instance, $P(1/3)$ is simply the probability that a random walk on $\mathbb{Z}$ starting at the origin and taking steps of $+2$ or $-1$ with equal probability will ever reach $-1$. If $f(n)$ is the probability of ever reaching a negative point given that the walk is currently at $n$, then $f(n)$ satisfies $$f(n) = \frac{f(n+2)+f(n-1)}2.$$ The standard ansatz $f(n) = x^n$ gives three solutions for $x$: $x=1$ or $x=(-1\pm \sqrt{5})/2$. It is easily seen that the only solution of the form $f(n) = Ax_1^n + Bx_2^n + Cx_3^n$ that satisfies the boundary conditions (at $-1$ and infinity) is $f(n) = (-1/2+\sqrt{5}/2)^{n+1}$, from which it follows that $$P(1/3) = \frac{\sqrt{5}-1}2.$$ Similarly, $P(1/2)$ is equal to the unique root of $x = (x^4+1)/2$ in $(0,1)$, and in general, $P(k/(k+2))$ is the unique relevant root of $x = (x^{k+2}+1)/2$.

If $\alpha$ is rational but not of this form, the boundary conditions become a little more complicated. For instance, consider $\alpha=1/5$. This can be modeled by a random walk on $\mathbb{Z}$ where a particle takes steps of $+3$ or $-2$. The corresponding ansatz gives $x^2 = (x^5+1)/2$, which has two roots of absolute value smaller than 1, one positive and one negative. Since the walk can now jump to the left, it can reach a first negative value both at $-1$ and at $-2$. Apart from $f(n)\to 0$ at infinity, we get the two boundary conditions $f(-1)=1$ and $f(-2)=1$. We can now find $f$ explicitly (at least numerically) as $f(n) = Ax_1^n+Bx_2^n$ where $x_1$ and $x_2$ are the roots in $(-1,1)$ and $A$ and $B$ are determined by the boundary conditions.

As has already been pointed out, $P(\alpha)$ makes a jump at every rational number. With the approach outlined above, one can in principle compute both the "lower" and "upper" values of $P(\alpha)$ (the upper value being the probability that $S_n$ reaches, but does not cross, the line of slope $\alpha$) whenever $\alpha$ is rational. This is feasible only when $\alpha$ is a relatively simple fraction, but it should still be possible to obtain a good plot of $P(\alpha)$ as a function of $\alpha$.

I recall that after this problem was discussed at the open problem session of FPSAC 2003, Pontus von Brömssen made some such plots. I haven't been in touch with him in the last few years, but apparently he has an (inactive) MO-account. I will notify him of this question.