Probability of ending on a certain point of a circle after randomly moving clockwise or counterclockwise, in succession.

Question

Suppose that $100$ points are equally spaced around a circular path, and at $99$ of these points there are sheep which do not move, and at the other point there is a wolf who will randomly move. Suppose that each time the wolf moves, he will be equally likely to move clockwise by one point or counterclockwise by one point, and if a sheep is at his new location he will eat it. If the wolf continues moving randomly until all of the sheep are eaten, what is the probability that the sheep who is located directly opposite the wolf’s starting point will be the last one eaten?

Start at a Solution:

I think there would be $2^{99}$ different ways the wolf could move.

Consider a more simple situation where there are $8$ points where the wolf starts at point $1$ and the points are numbered $1$-$8$ going clockwise. Then the wolf must end on point $5$. After writing out all the possibilities where it ends on $5$, it appears as if it initially has $2$ numbers to go to, followed by $4,6,6,4,2$. Then maybe with $10$ points it would be $2,4,6,8,8,6,4,2$. So perhaps there is a pattern but I don't know how I'd use it to find a solution.

Edit:

I think both of my above thoughts are incorrect because from my understanding, the wolf wouldn't skip points where no sheep are present.

Answer 1

Wolf will eventually reach next to the wanted sheep. It isn't matter will it be to the left or to the right. Now from that point wolf must go around the whole circle to reach the other neighbor sheep. So let wolf starting from that position and calculate probability to eat the sheep next to him last.

Since wolf will eventually come next to each of the sheep (it starts next to 2 of them) probability to be eaten last is same for all sheep, so probability is p=1/99

EDIT

Let $p(n)$ be probability to reach $n$th place to the left but never step on the place to the current right.

First, the wolf has to get to $n-1$-st place, so $p(n-1)$. Then, it has to get to one further left, before getting $n$ back to the right, which is exactly the opposite of what the original goal was! (To move $n$ left before even $1$ right; just reverse the meaning of left and right.) So the probability of that part is $1 - p(n)$, or together: $$ p(n)=p(n-1) (1 - p(n)) $$ $$ p(n) = \frac{p(n-1)}{1 + p(n-1)}. $$

We know $p(1)=\frac 1 2$

so $ p(n) = \frac {1}{n+1} $ by induction. $p(98)=\frac 1 {99}$ which is the probability you are looking for.

Answer 2

Here is what I think is a proper solution:

Number the points clockwise from 0 to n-1. Wolf is at 0 initially.

For a sheep to be last eaten, both of its neighbors should be eaten before it. So if sheep at location i is to be last eaten, the sheep at i-1 and i+1 must be eaten first. This can happen in two ways, either i-1 is eaten before i+1 or i+1 is eaten before i-1.

Let $A_i$ be the event that the ith sheep is last eaten and $B_{j,k}$ be the event that jth eaten before kth.

So $P(A_i)$ = $P(A_i | B_{i-1,i+1}) P(B_{i-1,i+1}) + P(A_i| B_{i+1,i-1}) P(B_{i+1,i-1})$

To calculate $P(B_{i-1,i+1})$, notice that this is exactly the Gambler's Ruin problem with gambler X starting with $n-1-(i+1)+1=n-i-1$ dollars and gambler Y starting with $i-1$ dollars and we are looking for the probability that X wins. Hence the total money is $(n-i-1)+(i-1) = n-2$ dollars. When the probability of X winning a single game is 1/2 (as in here where the wolf moves to right or left with probability 1/2) this is given by $\frac{n-i-1}{n-2}$ (See p65 Introduction to Probability, Blitzstein, Hwang)

Calculating $P(A_i | B_{i-1,i+1})$ means we are looking for the probability of the event where i+1 is eaten before i. So $P(A_i | B_{i-1,i+1})$ = $P(B_{i+1,i})$. Notice that this is another Gambler's Ruin problem with gambler X starting with 1 dollar and gambler Y starting with n-2 dollars and we are looking for the probability that gambler X wins. So $P(B_{i+1,i}) = \frac{1}{n-1}$

Similarly we find,

$P(B_{i+1,i-1}) = \frac{i-1}{n-2}$ and $P(A_i| B_{i+1,i-1}) = \frac{1}{n-1}$

Therefore $P(A_i)= \frac{n-i-1}{n-2} \frac{1}{n-1} + \frac{i-1}{n-2} \frac{1}{n-1} = \frac{1}{n-1}$