Random Walk on Ring City

Question

Ring City has 100 houses arranged in a circle. Alice starts at her own house, and every day she randomly moves to one of the two adjacent houses, each with 50% probability. She repeats this until she has visited all of the houses. Which house(s) is/are the most likely to be visited last?

Answer 1

John and Kevin are correct: the probability is the same, $\frac{1}{99}$, for each house except the one she begins at. Below is a mathematical argument for why this must be.

Let the houses be numbered in order, going around the circle, from #1 to #100, with #1 being the house she starts at. (Note that house #1 is between houses #2 and #100.)

Let $p_n$ denote the probability that the last house she visits is house #n.

Let $q_n$ denote the probability that the last house she visits is house #n, provided that the first house she randomly moves to is house #2.

Let $r_n$ denote the probability that the last house she visits is house #n, provided that the first house she randomly moves to is house #100.

The following observations are straightforward:

• Various probabilities are known to be zero: $p_1 = 0$ and $q_1 = 0$ and $q_2 = 0$ and $r_1 = 0$ and $r_{100} = 0$.
• By symmetry, $p_2 = p_{100}$, and $p_3 = p_{99}$, and so on, up through $p_{50} = p_{52}$.
• By symmetry, $q_3 = r_{99}$, and $q_4 = r_{98}$, and so on, all the way up through $q_{100} = r_2$.
• Since Alice must initially move to either house #2 or house #100, and either of these is equally likely, we know that $p_n = \frac{q_n + r_n}{2}$.

In addition, we need one somewhat-subtle observation: If she initially moves to house #2, then she "shifts" the probability of every house over by one house — so, for example, $q_3 = p_2$ — except that $q_1 = 0$ (instead of $q_1 = p_{100}$, which is not true) $q_{100} = p_{99} + p_{100}$. The reason that $q_{100} = p_{99} + p_{100}$ is that if we imagine that Alice initially moves to house #2 and then reset her memory (forgetting that she had already visited house #1), and therefore continues until she has visited every house at least once and house #1 at least twice, then if it indeed happens that her return to house #1 is her last move, then house #100 must have been her second-to-last house, because she had to visit #100 before re-visiting #1 (in order for her house #1 re-visit to be her last house), and the only way to get all the way to #100 before re-visiting #1 is to first visit every single house from #3 to #99.

Given those facts, the rest is algebra:

• $p_1 = 0$
• $p_2 = \frac{q_2 + r_2}{2} = \frac{r_2}{2} = \frac{q_{100}}{2} = \frac{p_{99} + p_{100}}{2} = \frac{p_2 + p_3}{2} \Rightarrow p_3 = p_2$
• $p_3 = \frac{q_3 + r_3}{2} = \frac{q_3 + q_{99}}{2} = \frac{p_2 + p_{98}}{2} = \frac{p_2 + p_4}{2} = \frac{p_3 + p_4}{2} \Rightarrow p_4 = p_3$
• $p_4 = \frac{q_4 + r_4}{2} = \frac{q_4 + q_{98}}{2} = \frac{p_3 + p_{97}}{2} = \frac{p_3 + p_5}{2} = \frac{p_4 + p_5}{2} \Rightarrow p_5 = p_4$
• ...

Answer 2

I wrote the following program to check the probabilities. Surprisingly, it appears the answer is that all houses have an equal probability of being visited last! The more likely a house is to be visited from one side, the less likely from the other side, and apparently those cancel out. See Ruakh's answer for a rigorous proof.

#include <stdio.h>
#include <stdlib.h>

#define N 100
#define TRIALS 100000

int go() {
    int doors[N] = {1};
    int unique = 1;
    int i = 0;
    while (unique < N) {
        i = (i + 2*arc4random_uniform(2) + N - 1)%N;
        if (doors[i] == 0) {
            unique++;
            doors[i] = 1;
        }
    }
    return i;
}

int main() {
    int doors[N] = {0};
    for (int i = 0; i < TRIALS; i++) {
        doors[go()]++;
    }
    for (int i = 0; i < N; i++) {
        printf("%d: %d\n", i+1, doors[i]);
    }
    return EXIT_SUCCESS;
}

Sample results [TRIALS = 10M]:

1: 0
2: 101527
3: 101171
4: 100559
5: 100836
6: 100708
7: 101287
8: 100198
9: 100880
10: 101034
11: 101746
12: 100797
13: 101113
14: 100255
15: 100268
16: 101401
17: 101076
18: 101165
19: 100811
20: 101339
21: 100836
22: 101519
23: 101056
24: 100544
25: 100960
26: 101046
27: 100687
28: 100987
29: 100801
30: 101123
31: 101045
32: 101195
33: 101462
34: 101302
35: 100930
36: 100672
37: 100794
38: 100362
39: 100957
40: 101342
41: 100819
42: 101464
43: 100824
44: 100810
45: 101009
46: 100797
47: 101409
48: 101267
49: 101176
50: 101398
51: 100872
52: 101328
53: 101060
54: 101174
55: 100592
56: 101091
57: 101059
58: 101357
59: 101020
60: 101002
61: 101168
62: 100612
63: 101208
64: 101341
65: 100329
66: 101180
67: 101474
68: 101442
69: 101302
70: 101537
71: 101158
72: 101082
73: 101007
74: 100812
75: 100826
76: 100542
77: 100244
78: 101250
79: 100853
80: 100696
81: 101522
82: 100750
83: 101193
84: 101617
85: 101515
86: 100634
87: 101384
88: 100391
89: 100587
90: 101050
91: 101382
92: 101077
93: 101155
94: 100603
95: 100357
96: 100809
97: 101075
98: 101054
99: 101308
100: 101155

Answer 3

The the last door index is a uniform distribution, with a constant probability of any door being last is 1/99, and the standard deviation after N evaluations is 2.3/sqrt(N).

I had to develop algorithms in order to have the program run faster enough in R. As I was making the algorithms, the following 2 arguments seem relevant.

1) The number of steps required to reach the last door is a random variable greater than 100. Hence, the location of the last door is a random variable. The door selection forms a rings, so there is no central point, so the random distribution is uniform. Every door, except the 1st, has a probability of 1/99 of being the last door.

2) A different argument, it doesn't matter what doors have been previously visited. So, the puzzle after visiting 50 doors, or N doors, is the same. The probability of reach the opposite door does not depend on the starting point, so there is no preference to the opposite door.

The heart of the proof is the convergence of the mean statistic and standard deviation trend as the number of evaluations increases. The mean percent occurrence is always 1.0101, starting with only 1 door (1/99). The standard deviation decreases exponentially as N increases.

Here is the plot of mean percentage as the number of iterations increases on a semilog scale (the mean percentage is a constant, 1.0101)

Here is the tread of standard deviation with increasing number of evaluations on a log log scale. The trend is linear, indicating that std_dev ~ 2.3*sqrt(N)

Here's an R script to tabulate the frequency of the last door. The algorithm is

1) Find a random walk that covers all 100 doors
2) Determine the length of the random walk to cover 99 doors
3) The last door is whatever door is remaining
4) Repeat steps 1 to 3 for a range of iterations, then plot the mean/std

# 100 houses in a ring
# random move to either side
# What is the probability of door being last
cat("\014") 
doMoves <- function() {
  doorVec <- rep(1,100)
  currentDoor = 1
  doorVec[currentDoor] = 0
  nUnique = 1
  # Find sequence longer than than required to visit all doors
  houseDoors = c(1)
  nDoorsToAdd = 1000
  while(nUnique < 100) {
    randMoves <- sample(c(-1,1),nDoorsToAdd,replace=TRUE)
    currentDoor <- houseDoors[length(houseDoors)]
    newHousesVisited <- currentDoor+cumsum(randMoves)
    houseDoors <- ((c(houseDoors, newHousesVisited)-1) %% 100)+1
    nUnique = length(unique(houseDoors))
  }
  # Find lenght of sequence required to visit 99 doors
  maxMovesRequired = length(houseDoors) 
  minMovesRequired = maxMovesRequired - nDoorsToAdd
  nMovesToTry <- minMovesRequired
  nDoorsVisited <- length(unique(houseDoors[1:nMovesToTry]))
  while(nDoorsVisited != 99) {
    nMovesToTry <- floor((minMovesRequired+maxMovesRequired)/2)
    nDoorsVisited = length(unique(houseDoors[1:nMovesToTry]))
    if (nDoorsVisited<99) {
      minMovesRequired = nMovesToTry
    } else if (nDoorsVisited>99) {
      maxMovesRequired = nMovesToTry
    }
  }
  # Find the last door
  lastDoor <- setdiff(1:100,unique(houseDoors[1:nMovesToTry]))

  return(lastDoor)
}

findLastDoors <- function(nTries) {
  lastDoorCount <- rep(0,100)
  for (iTry in seq(1,nTries)) {
    lastDoor <- doMoves()
    lastDoorCount[lastDoor] = lastDoorCount[lastDoor]+1
  }
  return(lastDoorCount)
}
doIt <- function(n) {
  lastDoorCount <- findLastDoors(n)
  print(paste(sum(lastDoorCount),'samples'))
  ld_mn <- mean(lastDoorCount[-1]/n*100)
  ld_st <- sd(lastDoorCount[-1]/n*100)
  plot(lastDoorCount[-1])
  plot(lastDoorCount[-1]/n*100,xlab="Door",ylab="Percent Times Last",
       main=sprintf('%d doors has mean %.6f std dev %.4f',n,ld_mn,ld_st))
  print(lastDoorCount[-1])
  print(lastDoorCount[-1]/n*100)
  print(sprintf('%d doors has mean %.6f std dev %.4f',n,ld_mn,ld_st))
  return(list(n=n, ldc = lastDoorCount, ld_mn = ld_mn, ld_std = ld_st))
}
print(system.time(r1<-doIt(1L)))
print(system.time(r5<-doIt(5L)))
print(system.time(r10<-doIt(10L)))
print(system.time(r50<-doIt(50L)))
print(system.time(r100<-doIt(100L)))
print(system.time(r500<-doIt(500L)))
print(system.time(r1000<-doIt(1000L)))
print(system.time(r5000<-doIt(5000L)))
#print(system.time(r10000<-doIt(10000L)))
#print(system.time(r10000<-doIt(50000L)))
#print(system.time(r100000<-doIt(100000)))
#print(system.time(r100000<-doIt(1000000)))

smry<-data.frame(n=c(r1$n,r5$n,r10$n,r50$n,r100$n,
                     r500$n,r1000$n,r5000$n),
                 ld_mn=c(r1$ld_mn,r5$ld_mn,r10$ld_mn,r50$ld_mn,r100$ld_mn,
                     r500$ld_mn,r1000$ld_mn,r5000$ld_mn),
                 ld_std=c(r1$ld_std,r5$ld_std,r10$ld_std,r50$ld_std,r100$ld_std,
                     r500$ld_std,r1000$ld_std,r5000$ld_std))
plot(smry$n,smry$ld_mn,log='x',xlab='N Iterations',ylab='Mean Percetage')
plot(smry$n,smry$ld_std,log='xy',xlab='N Iterations',ylab='Std Dev Percetage')

Here's a plot of the percent frequencies for 500 and 5000 evaluations. The distribution is uniform, constant mean of 1.0101 percent, and reduced standard deviation for increasing number of evaluations.

Answer 4

It turns out that while this is correct is doesn't not answer the question. I will leave it here on the off chance that it's useful to anyone. It does answer a question that noone asked.

If she starts at house $h_1$ and the adjacent houses are houses $h_2$ (to the left) and $h_{100}$ (to the right). Probabilistically she will visit house $h_{51}$ last (the one most directly opposite).

Let's consider a much simpler case. $4$ houses. She starts at house $h_1$ and the adjacent houses are houses $h_2$ (to the left) and $h_4$ (to the right). She's already been to $h_1$. There is now probability $0.5$ of visiting house $h_2$ next (similarly for house $h_4$). From there there is a $0.5$ probability of visiting house $h_3$. And since there are two ways to reach $h_3$ we must double the probability of having arrived from one side, $0.25$, and see that there is a probability of $0.5$ of visiting house $h_3$ for the first time in $2$ moves.

Now let's scale back up. The probabilty of visiting house $h_{51}$ for the first time after $50$ steps is $1/2^{49}$. This is lowest probability that any house has to be visited for the first time.