Return to JUNTO

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 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.

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 pi for each i is

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:

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%