# JUNTO Practice: Probability, Numbers on a Circle

Discussed on June 04, 2020.

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 each i, compute the probability pi that, when the walker is at i for the first time, all other points have been previously visited, i.e., that i is the last new point. For example, p0 = 0.

## Solutions

Click to see:

### Oscar Martinez

``````import random

def final_point(n):
points = list(range(n))
visited_all = False
visits = 
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 pi for each i is

• p0 = 0
• p1 = (n - 1)-1
• p2 = (n - 1)-1
• ...
• pn = (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):
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...

• 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%
``````