Probability of Discovering (N-1)st Point on a Circle

[Alexei]

The circle has N points equally spaced where a transition from one point to one of the two adjacent ones is done with p = q = 1/2 - the symmetric random walk.

Let there be ordered points r - 1, r, and r + 1 located somewhere on a circle with r E {1, ..., N}. What is the probability that the discovered for a first time (N-2)st point is point r + 1 or r - 1?

P(X_T(n-2) = r+1) - ?
P(X_T(n-2) = r-1) - ?

Where T(x) - designates the time (number of transitions) when the number of distinct points discovered is x. X_T(x) is a r.v. representing a particular point from {1, ..., N} when discovery of x is done.

 

[pruse]

You've gotta clarify some points (heheh) here... 1) Are the points numbered in order and we start at point #1? 2) Are you asking for the probability that the (N-2)-st distinct point to be hit is either r+1 or r-1?

 

[Brad Warren]

I assume the points are ordered 1 to N, we start at point 1, the (N – 2)-nd distinct point is the point we reach such that there are 2 points we have not visited, and the starting point counts as visited.

Let X(t) be a stochastic process such that X(0) = 0 and it either increments or decrements by 1 each time step with equal probability. It is easy to see X(t) is a martingale. Now let Y(t) = X(t) % N + 1 be our position at time t in the circle.

We want to calculate the probability P(p) of reaching a point p without visiting point q, given our current position Y(t). Let dist(p) be the distance we need to travel to reach p and dist(q) be the distance we need to travel in the other direction to reach q. The time taken to reach one of these points is a stopping time with finite expectation. Assuming p is in the positive direction (the probability does not change because of symmetry), the expected value E[dX(t)] = P(p)dist(p) - (1 – P(p))dist(q). Because X(t) is a martingale, this expectation is equal to zero and P(p) = dist(q) / (dist(p) + dist(q)).

Let x, y be points 3 away from each other. Point x is the (N – 2)-nd distinct point iff we reach point y without visiting x or the 2 points in between, and then make a trip around the circle to point x so that the only unvisited points are those 2 in between x and y. For the final trip, we travel N – 3 points without visiting the point 1 away in the other direction. Using the formula above, with dist(p) = N – 3 and dist(q) = 1, we calculate the probability P(x | y) = 1 / (N – 2). This is the probability x is the (N – 2)-nd distinct point given that we reached point y without visiting x or the points in between. Now we need to find the probability of reaching point y without visiting x or the points in between, and starting at point 1. There are 4 cases:

\(x=r+1, y=r-2:\\dist(x)=(1+N)-(r+1)=N-r\\dist(y)=(r-2)-1=r-3\\P(y)=\frac{N-r}{N-3}, r\geq3\\P(y)=0, r<3\)(x=r+1, y=r+4:\\dist(x)=(r+1)-1=r\\dist(y)=(1+N)-(r+4)=N-r-3\\P(y)=\frac{r}{N-3}, r\leq N-3\\P(y)=0, r>N-3\)
\(x=r-1, y=r-4:\\dist(x)=(1+N)-(r-1)=N-r+2\\dist(y)=(r-4)-1=r-5\\P(y)=\frac{N-r+2}{N-3}, r\geq5\\P(y)=0, r<5\)
\(x=r-1, y=r+2:\\dist(x)=(r-1)-1=r-2\\dist(y)=(1+N)-(r+2)=N-r-1\\P(y)=\frac{r-2}{N-3}, r\leq N-1\\P(y)=0, r=N\)

Adding the probabilities of the disjoint cases together, and multiplying by P(x | y) = 1 / (N – 2) yields the solution, the probability that the (N – 2)-nd distinct point is r + 1 or r – 1. For the trivial cases N = 3 or N = 4, the probabilities are always 0 or 1 depending on r. For N > 4:

\(P(r+1)=\frac{r}{(N-2)(N-3)}, r\leq2\)
\(P(r+1)=\frac{N}{(N-2)(N-3)}, 2<r\leq N-3\)
\(P(r+1)=\frac{N-r}{(N-2)(N-3)}, r>N-3\)
\(P(r-1)=\frac{r-2}{(N-2)(N-3)}, r\leq4\)
\(P(r-1)=\frac{N}{(N-2)(N-3)}, 4<r\leq N-1\)
\(P(r-1)=\frac{2}{(N-2)(N-3)}, r=N\)

 

[Brad Warren]

Huh, I posted it twice, edited one, and now the other is gone.

The probabilities of the (N-2)-nd point being r + 1 or r - 1 are:

\(P(r+1)=\frac{r}{(N-2)(N-3)}\) , \(r\leq2\)
\(P(r+1)=\frac{N}{(N-2)(N-3)}\) , \(2<r\leq N-3\)
\(P(r+1)=\frac{N-r}{(N-2)(N-3)}\) , \(r>N-3\)

\(P(r+1)=\frac{r-2}{(N-2)(N-3)}\) , \(r\leq4\)
\(P(r+1)=\frac{N}{(N-2)(N-3)}\) , \(4<r\leq N-1\)
\(P(r+1)=\frac{2}{(N-2)(N-3)}\) , \(r=N\)

 

[Brad Warren]

The second set is for r - 1:

\(P(r+1)=\frac{r}{(N-2)(N-3)}\) , \(r\leq2\)
\(P(r+1)=\frac{N}{(N-2)(N-3)}\) , \(2<r\leq N-3\)
\(P(r+1)=\frac{N-r}{(N-2)(N-3)}\) , \(r>N-3\)

\(P(r-1)=\frac{r-2}{(N-2)(N-3)}\) , \(r\leq4\)
\(P(r-1)=\frac{N}{(N-2)(N-3)}\) , \(4<r\leq N-1\)
\(P(r-1)=\frac{2}{(N-2)(N-3)}\) , \(r=N\)