6
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ I think it is easier to cut the circle at the 50th sheep. Then it is a random walk starting at 0, in which you want the probability of reaching 50 after -49 but before -50 or reaching -50 after 49 but before 50. $\endgroup$ Commented Sep 30, 2017 at 18:05
  • $\begingroup$ This is a good idea. $\endgroup$
    – Remy
    Commented Sep 30, 2017 at 18:06
  • $\begingroup$ So going clockwise from $0$ how are you counting? $(0,1,2,...,50,-49,-48,...,-1)$? $\endgroup$
    – Remy
    Commented Sep 30, 2017 at 18:09

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ @NickPavlov sorry I opened edit window long ago and didn't see you edited the answer. Is it the same result like mine? $\endgroup$ Commented Sep 30, 2017 at 21:31
  • $\begingroup$ Are you saying that all sheep are equally likely to be the last one standing? Perhaps it needs a bit more of an explanation... EDIT: Never mind, I got it, but still, the argument now looks a bit too... simplistic. Brilliant, though. Can't believe how much time I spent figuring it out my way... $\endgroup$ Commented Sep 30, 2017 at 21:37
  • $\begingroup$ @NickPavlov Actually I got to that probability on hard way and then I realized the simplicity :) $\endgroup$ Commented Sep 30, 2017 at 21:44
  • $\begingroup$ I feel dumb now. I'm still confused though. I feel as though more things have to go right for it to end up on the 50th sheep than, say, the 99th sheep. $\endgroup$
    – Remy
    Commented Sep 30, 2017 at 22:10
  • 1
    $\begingroup$ @JohnH Not to be immodest, but I think my version of the detailed argument (i.e. the induction for $p(n)$ - what Djura has added in the last edit) was simpler. It's still in the revision history at #2. $\endgroup$ Commented Oct 4, 2017 at 9:14
1
$\begingroup$

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}$

$\endgroup$
0
$\begingroup$

I'm providing another answer because I believe it is much shorter and concise than other answers

you can map the points on the circle to real line where $1, 2, \ldots 51$ are mapped to $0, 1, \ldots, 50$ and $100, 99, \ldots, 51$ are mapped to $-1, -2, \ldots, -50$

So our desired probability = $1 - $ prob(wolf reaches $50$ before $-49$ or wolf reaches $-50$ before $49$) = $1 - 2 \times \frac{49}{(49 + 50)} = \frac{1}{99}$

here I'm just using the well known fact that probability of reaching $a$ before $-b$ for a random walk starting at $0$ is $\frac{b} {a+b}$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .