# Probability of two points being split into different partitions.

Suppose $x < y \in [0, 1]$ and $U_1, U_2, ...$ are random variables distributed as uniform on $(0, w)$ with $w < 1$. Define $S_n = \sum_{i = 1} ^ n U_i$. We'll say that $(S_i)$ splits $x$ and $y$ if, for some $n$, $x < S_n < y$. I'm interested in what sorts of things could be said about the probability that $x$ and $y$ are split. If it helps, take $w$ to be small and $x, y$ close to $1$ and $|x - y| < w$.

I feel that this is quite related to whatever subject studies things like Poisson processes. Obviously, I know that if $|x - y| > w$ then $x$ and $y$ will be split, but beyond that I'm not sure what theory I would look to, and I don't know whether this sort of problem is tractable or not (it might be trivial for all I know). Only guess that I have is that near $|x - y| = w$ the probability should go to $0$ like $1 - \frac{|x - y|}{w}$, and this should be a lower bound for any $|x - y| < w$. I may also be interested in results or pointers for $U_i$ not uniform, but I need it to be the case that for points sufficiently far away the probability of being split is exactly $1$.

EDIT: In light of the solution posted by PinkElephant below, I'll reword this as follows. Set $w = 1$ and remove the restriction on $x, y \in [0, 1]$ so that just $x < y \in \mathbb R$. What is the probability that $x$ and $y$ are split for large values of $x, y$ but for $|x - y|$ fixed, i.e. $x, y \to \infty$ but $y - x$ constant. It seems to me that asymptotically things should only depend on $y - x$; for $x, y$ near $0$ it seems as though there is dependence on the fact that we started the sum from $0$ that I think we escape from for large $x, y$.

Update: I have a heuristic argument that gives the asymptotic probability of $x$ and $y$ being split as $1 - (1 - |x - y|)^2_+$ where $(a)_+$ denotes $\max\{0, a\}$. The argument is as follows: it should not matter asymptotically where $x$ and $y$ lie, so we can assume $x= k$ for some positive integer $k$. $x$ and $y$ will be split if, for the first value of $S_i$ in the interval $[x, x + 1]$, we have $x \le S_i \le y$. Consider the Markov chain $T_j$ consisting of the fractional parts of those $S_i$ such that $(S_{i - 1}) > (S_i)$, where $(a)$ denotes the fractional part of $a$. The probability that $x$ and $y$ are split should be $P(T \le (y - x))$ where $T$ is drawn from the stationary distribution of the $T_j$. I took a blind guess that the stationary distribution was given by the density $f(t) = 2(1 - t)$, drew a bunch of samples from the Markov chain I described, and verified empirically that $f(t) = 2 (1 - t)$ is the answer I'm supposed to get.

If anyone wants to take a stab at verifying that $1 - (1 - |x - y|)_+^2$ is indeed the correct answer asymptotically, it would be much appreciated.

• you are talking about the renewal measure for that process and it is asymptotocally uniform, by the renewal thm – mike Dec 13 '12 at 13:45
• @mike I'm not sure off the top of my head what is wrong with that logic, but empirically I'm certain it is not uniform. The chain clearly has a higher probability of transferring to a smaller value than its current one. – guy Dec 13 '12 at 14:12
• you are right, you don't want the expected number of visits, which is uniform, but you do want the probability of one visit for that process, which is related to the excess life, or excess over the boundary rv, and I think it turns out as you say. – mike Dec 13 '12 at 15:12

## 2 Answers

Given $x$, let $S_x$ be the random variable $S_{\min \{n, S_n \ge x\}}$. It has values in $[x;x+1]$, and let $g_x(y)$ be its density : $\forall x \le y_1 \le y_2 \le x+1, \int_{y_1}^{y_2} g_x(y)dy = P(S_x \in [y_0;y_1])$.

As $x$ grows, the weight put on $g_x(y)$ for $y$ near $x$ is displaced and redistributed to all the other $y \in [x;x+1]$. In particular, if $x_1 \le x_2 \le y_1 \le y_2 \le x_1+1$, then $y_1$ and $y_2$ receive the same amount of weight when going from $x_1$ to $x_2$, so : $g_{x_2}(y_1) - g_{x_1}(y_1) = g_{x_2}(y_2) - g_{x_1}(y_2)$, and this implies that the function $g_x(y_2)-g_x(y_1)$ is constant for the range of $x$ where it makes sense.

From this we can deduce that there are two functions $F(x),G(y)$ such that $g_x(y) = G(y)+F(x)$ whenever $g_x(y)$ makes sense.

Now, we must have that forall $x>1$, $g_x(x+1)=0$, thus $F(x) = -G(x+1)$, and so $g_x(y) = G(y)-G(x+1)$. Moreover, forall $x$, $1 = \int_x^{x+1} g_x(y)dy = -G(x+1)+ \int_x^{x+1} G(y)dy$. Differentiating this you get $0 = -G'(x+1)+G(x+1)-G(x)$, so the problem reduces to studying the delay differential equation $$f'(x) = f(x) - f(x-1)$$

Our initial condition is $G(x) = 1$ for $0 \le x < 1$, and $G(1)=0$. The goal is to show that for $a \in [0;1], G(x) - G(x+a) = 2a + o(1)$.

The solution we are interested in can be defined piece by piece, it turns out that $G(x+1) = 1 - e^x\sum_{0 \le k \le x} (\frac{k-x}e)^k/k!$

Suppose $f$ is a solution to the differential equation. Put $g(x) = \int_{x-1}^x f(t) dt - f(x)$. Then $g'(x) = f(x) - f(x-1) -f'(x) = 0$. So $g(x) = C$ and by substracting $2Cx$ from $f(x)$, we can assume without loss of generality that $g(x) = 0$.

Define $h(x) = \int_{x-1}^x (f(t)-f(x))^2 dt$. Then $$h'(x) = (f(x)^2 - f(x-1)^2) -2(f(x)^2-f(x-1)f(x)+f'(x)\int_{x-1}^x f(t)dt) + 2f(x)f'(x) \\ = (f(x)^2 - f(x-1)^2) -2(f(x)^2-f(x-1)f(x)) = -(f(x-1)-f(x))^2 = -f'(x)^2$$ $h$ is obviously positive, and decreasing, so it has a limit, and in particular, for any $a\in [0;1], h(x)-h(x+a) \to 0$, uniformly in $a$.

Finally, $(f(x+a)-f(x))^2 = \left(\int_x^{x+a} f'(t)dt \right)^2 \le a \int_x^{x+a} f'(t)^2 dt = a(h(x+a) - h(x)) \to 0$. Hence in the original context, $g_x(y) \to 0$ (uniformly) as $x \to \infty$

• Very interesting, it will take some time to digest I think. On the Markov chain train of thought, I think I could get the result if I could show that the step assuming $x = k$ for an integer $k$ WLOG is justified, since then I think I could just show the distribution $f(t) = 2(1 - t)$ is a fixed-point of the chain I described. – guy Dec 14 '12 at 18:46
• @guy : I think I completed the proof. – mercio May 6 '13 at 10:29

If we scale $x$, $y$, and $w$ by the same positive constant, the answer is unchanged, so for simplicity I will take $w=1$ and remove the restriction that $x,y\in[0,1]$. Define $f(x,y)$ to be the probability that $x$ and $y$ are split. For arbitrary $w$, the probability that $x$ and $y$ are split is $f\left(\frac{x}{w},\frac{y}{w}\right)$.

For $0<x\leq y$, $f(x,y)$ satisfies the equation $$f(x,y)=\int_0^1f(x-t,y-t)\,dt$$ (We extend $f(x,y)$ to the region $\{y\geq x\}\subset\mathbb{R}^2$ by setting $f(x,y)=1$ for $x<0$, $y\geq0$, and $f(x,y)=0$ for $x<y<0$)

This equation can be differentiated to give the differential-delay equation $$f_x(x,y)+f_y(x,y)=f(x,y)-f(x-1,y-1)$$

The solution is piecewise real-analytic, with boundaries between the pieces lying on the lines $y=x$, $y=x+1$, the line segments $y\in [x,x+1],x\in\mathbb{Z}_{\geq0}$, and the line segments $y\in[x,x+1],y\in\mathbb{Z}_{\geq0}$.

It's not too hard to recursively compute values of $f(x,y)$ on the various pieces of the domain. I computed some values with Mathematica:

For $0<x\leq y<1$, $f(x,y)=(y-x)e^x$.

For $0<x\leq 1\leq y\leq x+1$, $f(x,y)=(y-x)e^x+1-e^{y-1}$.

For $1\leq x\leq y\leq 2$, $f(x,y)=e^{x-1}-e^{y-1}+e^x\left(x^2-2x+2y-xy\right)$.

If you want to compute a specific value of $f(x,y)$ exactly, I don't know if there's a faster way than to continue this recursive computation. If you're only interested in the limiting value as $x,y\to\infty$ with $y-x$ fixed, this might be possible to compute.

• Thanks, I'll take a look at this. The limiting case is of special interest to me. I managed to calculate the probability of $x = 1/2$ and $y = 1$ being split by hand using a different technique (I was able to break things up by the probability of splitting in a fixed number of moves) and thankfully it agrees with this. – guy Dec 10 '12 at 2:53
• Could you elaborate on how you got the values of the functions on the particular regions? I don't have mathematica at my disposal, and I have absolutely no experience with PDEs or DDEs. I would consider a solution as $x, y \to \infty$ and $y - x$ fixed very interesting. I would be very happy if I could solve this problem. – guy Dec 11 '12 at 22:29
• I'm not sure that the last equation can be right; $f(x, y)$ is not monotone as a function of $y$ for fixed $x$. However, if $y < y'$ then $x$ and $y$ being split implies that $x$ and $y'$ are split, so that $f(x, y) \ge f(x, y')$. – guy Dec 12 '12 at 2:03
• Also, it can take negative values. – guy Dec 12 '12 at 2:12