# JUNTO Practice: Probability, Numbers on a Circle

Discussed on June 04, 2020.

From "Twenty problems in probability":

You have

n> 1 numbers 0, 1, ... ,n−1 arranged on a circle. A random walker starts at 0 and at each step moves at random to one of its two nearest neighbors. For eachi, compute the probability p_{i}that, when the walker is atifor the first time, all other points have been previously visited, i.e., thatiis the last new point. For example, p_{0}= 0.

Please provide an answer and a justification.

## Solutions

Click to see:

### Oscar Martinez

```
import random
def final_point(n):
points = list(range(n))
visited_all = False
visits = [0]
while not visited_all:
current_point = visits[len(visits) - 1]
move = 1 + (random.randint(0,1) * -2)
new_point = current_point + move
if new_point >= len(points):
new_point = new_point - len(points)
visits.append(points[new_point])
if len(set(visits)) == n:
visited_all = True
return visits[len(visits) - 1]
```

### John Lekberg

For `n` numbers arranged on a circle, I think that probability
p_{i} for each `i` is

- p
_{0}= 0 - p
_{1}= (`n`- 1)^{-1} - p
_{2}= (`n`- 1)^{-1} - ...
- p
_{n}= (`n`- 1)^{-1}

I created a Python function to sample the random variable "the last new point of the random walk":

```
import random
def random_last_new_point(n):
"""Sample the random variable "the last new
point of the random walk".
"""
rand = random.random
i = 0
remaining = [True] * n
n_remaining = n
while n_remaining > 1:
if remaining[i]:
remaining[i] = False
n_remaining -= 1
if rand() < 0.5:
i = (i - 1) % n
else:
i = (i + 1) % n
for i in range(n):
if remaining[i]:
return i
```

And I created a function to generate a random sample and report the probabilities:

`import collections def report(*, circle_n, sample_n): table = collections.Counter( random_last_new_point(circle_n) for _ in range(sample_n) ) freq = lambda i: table[i] / sample_n print(f"circle_n={circle_n} ; sample_n={sample_n:,}") for i in range(circle_n): pad = len(str(circle_n)) - len(str(i)) print( f"Prob({i}) {' ' * pad}= {freq(i):6.2%}" ) report(circle_n=10, sample_n=1_000_000)`

```
circle_n=10 ; sample_n=1,000,000
Prob(0) = 0.00%
Prob(1) = 11.08%
Prob(2) = 11.14%
Prob(3) = 11.11%
Prob(4) = 11.11%
Prob(5) = 11.08%
Prob(6) = 11.15%
Prob(7) = 11.16%
Prob(8) = 11.06%
Prob(9) = 11.11%
```

`report(circle_n=11, sample_n=1_000_000)`

```
circle_n=11 ; sample_n=1,000,000
Prob(0) = 0.00%
Prob(1) = 9.97%
Prob(2) = 10.05%
Prob(3) = 10.02%
Prob(4) = 10.03%
Prob(5) = 9.96%
Prob(6) = 9.97%
Prob(7) = 9.97%
Prob(8) = 10.05%
Prob(9) = 9.99%
Prob(10) = 9.99%
```

`report(circle_n=26, sample_n=1_000_000)`

```
circle_n=26 ; sample_n=1,000,000
Prob(0) = 0.00%
Prob(1) = 4.01%
Prob(2) = 3.99%
Prob(3) = 3.98%
Prob(4) = 3.99%
Prob(5) = 3.98%
Prob(6) = 4.00%
Prob(7) = 4.02%
Prob(8) = 4.02%
Prob(9) = 4.02%
Prob(10) = 4.00%
Prob(11) = 4.00%
Prob(12) = 4.03%
Prob(13) = 4.01%
Prob(14) = 4.02%
Prob(15) = 4.01%
Prob(16) = 4.00%
Prob(17) = 4.02%
Prob(18) = 4.02%
Prob(19) = 3.99%
Prob(20) = 4.00%
Prob(21) = 4.01%
Prob(22) = 3.96%
Prob(23) = 3.98%
Prob(24) = 4.00%
Prob(25) = 3.95%
```

### Daniel Bassett

I ran short on time, so I ended up integrating John's solution with mine to solve my debugging issues...

Answer:

- P(0) = 0
- P(n) = 1 / (n - 1)

I ran an experiment using Python that was modeled on John Lekberg's solution. I three functions: one that simulates the random walk, one that generates the random sample, and a main function used to input the size of the circle and iterations.

`from collections import Counter import random # This program uses code originally written by John # Lekberg as a model. def main(): test_run(size=20, iterations=100_000) test_run(size=50, iterations=100_000) test_run(size=100, iterations=100_000) def test_run(*, size, iterations): run = Counter( circle_walk(size) for _ in range(iterations) ) print(f"size={size} iterations={iterations}") freq = lambda i: run[i] / iterations for i in range(size): print(f"Probability({i}) = {freq(i):7.3%}") def circle_walk(steps): left = steps steps_left = steps * [True] x = 0 while left > 1: if steps_left[x]: steps_left[x] = False left = left - 1 if random.random() > 0.5: x = (x + 1) % steps else: x = (x - 1) % steps for x in range(steps): if steps_left[x]: return x main()`

```
size=20 iterations=100000
Probability(0) = 0.000%
Probability(1) = 5.366%
Probability(2) = 5.288%
Probability(3) = 5.278%
Probability(4) = 5.246%
Probability(5) = 5.151%
Probability(6) = 5.376%
Probability(7) = 5.160%
Probability(8) = 5.232%
Probability(9) = 5.279%
Probability(10) = 5.272%
Probability(11) = 5.215%
Probability(12) = 5.324%
Probability(13) = 5.185%
Probability(14) = 5.249%
Probability(15) = 5.325%
Probability(16) = 5.346%
Probability(17) = 5.209%
Probability(18) = 5.230%
Probability(19) = 5.269%
size=50 iterations=100000
Probability(0) = 0.000%
Probability(1) = 2.048%
Probability(2) = 2.029%
Probability(3) = 2.053%
Probability(4) = 2.075%
Probability(5) = 2.024%
Probability(6) = 1.974%
Probability(7) = 1.997%
Probability(8) = 2.083%
Probability(9) = 2.088%
Probability(10) = 2.002%
Probability(11) = 1.998%
Probability(12) = 2.076%
Probability(13) = 2.017%
Probability(14) = 2.119%
Probability(15) = 2.013%
Probability(16) = 1.970%
Probability(17) = 2.045%
Probability(18) = 2.122%
Probability(19) = 2.147%
Probability(20) = 2.044%
Probability(21) = 2.017%
Probability(22) = 2.110%
Probability(23) = 2.065%
Probability(24) = 2.061%
Probability(25) = 2.056%
Probability(26) = 2.062%
Probability(27) = 2.132%
Probability(28) = 2.005%
Probability(29) = 1.994%
Probability(30) = 2.044%
Probability(31) = 2.022%
Probability(32) = 2.082%
Probability(33) = 2.031%
Probability(34) = 2.012%
Probability(35) = 2.020%
Probability(36) = 2.100%
Probability(37) = 1.941%
Probability(38) = 2.083%
Probability(39) = 2.076%
Probability(40) = 2.067%
Probability(41) = 1.993%
Probability(42) = 2.058%
Probability(43) = 1.929%
Probability(44) = 1.986%
Probability(45) = 2.033%
Probability(46) = 1.990%
Probability(47) = 2.020%
Probability(48) = 2.008%
Probability(49) = 2.079%
size=100 iterations=100000
Probability(0) = 0.000%
Probability(1) = 1.031%
Probability(2) = 1.014%
Probability(3) = 1.030%
Probability(4) = 1.025%
Probability(5) = 1.057%
Probability(6) = 0.967%
Probability(7) = 1.019%
Probability(8) = 0.984%
Probability(9) = 0.997%
Probability(10) = 1.017%
Probability(11) = 0.997%
Probability(12) = 0.964%
Probability(13) = 1.040%
Probability(14) = 1.018%
Probability(15) = 1.015%
Probability(16) = 1.020%
Probability(17) = 0.986%
Probability(18) = 0.991%
Probability(19) = 1.015%
Probability(20) = 0.996%
Probability(21) = 0.976%
Probability(22) = 0.983%
Probability(23) = 0.988%
Probability(24) = 1.021%
Probability(25) = 1.057%
Probability(26) = 1.008%
Probability(27) = 1.004%
Probability(28) = 1.017%
Probability(29) = 0.984%
Probability(30) = 0.992%
Probability(31) = 0.961%
Probability(32) = 1.012%
Probability(33) = 0.995%
Probability(34) = 0.983%
Probability(35) = 1.054%
Probability(36) = 0.985%
Probability(37) = 0.942%
Probability(38) = 1.021%
Probability(39) = 0.996%
Probability(40) = 1.019%
Probability(41) = 0.955%
Probability(42) = 1.018%
Probability(43) = 1.022%
Probability(44) = 0.967%
Probability(45) = 1.024%
Probability(46) = 1.057%
Probability(47) = 0.997%
Probability(48) = 1.009%
Probability(49) = 1.021%
Probability(50) = 1.007%
Probability(51) = 0.950%
Probability(52) = 1.035%
Probability(53) = 1.005%
Probability(54) = 1.021%
Probability(55) = 1.072%
Probability(56) = 0.992%
Probability(57) = 1.041%
Probability(58) = 0.957%
Probability(59) = 1.086%
Probability(60) = 1.035%
Probability(61) = 1.055%
Probability(62) = 1.043%
Probability(63) = 0.959%
Probability(64) = 1.025%
Probability(65) = 1.031%
Probability(66) = 1.033%
Probability(67) = 0.987%
Probability(68) = 1.032%
Probability(69) = 0.995%
Probability(70) = 1.024%
Probability(71) = 1.015%
Probability(72) = 1.002%
Probability(73) = 0.983%
Probability(74) = 1.081%
Probability(75) = 0.991%
Probability(76) = 1.047%
Probability(77) = 1.014%
Probability(78) = 1.048%
Probability(79) = 1.005%
Probability(80) = 1.009%
Probability(81) = 1.049%
Probability(82) = 1.018%
Probability(83) = 1.001%
Probability(84) = 1.001%
Probability(85) = 1.027%
Probability(86) = 1.028%
Probability(87) = 0.968%
Probability(88) = 1.051%
Probability(89) = 1.012%
Probability(90) = 0.966%
Probability(91) = 1.036%
Probability(92) = 1.010%
Probability(93) = 1.007%
Probability(94) = 1.036%
Probability(95) = 0.980%
Probability(96) = 0.951%
Probability(97) = 1.028%
Probability(98) = 1.017%
Probability(99) = 0.983%
```