Setup

set.seed(516)
library(tidyverse)
## Warning: package 'tidyverse' was built under R version 4.3.3
## Warning: package 'ggplot2' was built under R version 4.3.3
## ── Attaching core tidyverse packages ──────────────────────── tidyverse 2.0.0 ──
## ✔ dplyr     1.1.4     ✔ readr     2.1.5
## ✔ forcats   1.0.0     ✔ stringr   1.5.1
## ✔ ggplot2   3.5.0     ✔ tibble    3.2.1
## ✔ lubridate 1.9.3     ✔ tidyr     1.3.0
## ✔ purrr     1.0.2     
## ── Conflicts ────────────────────────────────────────── tidyverse_conflicts() ──
## ✖ dplyr::filter() masks stats::filter()
## ✖ dplyr::lag()    masks stats::lag()
## ℹ Use the conflicted package (<http://conflicted.r-lib.org/>) to force all conflicts to become errors
library(viridis)
## Loading required package: viridisLite
library(gifski)
## Warning: package 'gifski' was built under R version 4.3.3
library(gganimate)
## Warning: package 'gganimate' was built under R version 4.3.3

Question 1

\(A_n\) grows by one element for each increase of \(n\). The maximum possible range of \(A_{n+1}\) is \((min(A_n) - K, max(A_n) + K)\).

Question 2

We considered 100 steps with \(K = 3\) instead after talking to Siva since it is easier to properly visualise the plot in that fashion.

simulate.An = function(steps, K = 2) {
    if(K < 2) {
        stop("K needs to be greater than or equal to 2")
    }

    # initial value of An, i.e., A0
    An = c(0)
    step.count = 0
    points = list()
    points[[step.count + 1]] = An

    while(step.count != steps) {
        for(i in 1:K) {
            neighbours = c()
            for(elem in An) {
                neighbours = c(neighbours, elem + 1, elem - 1)
            }
    
            # Removing any possible elements of An in the list of neighbours
            neighbours = neighbours[! (neighbours %in% An) ]
            newElem = sample(neighbours, size = 1, replace = FALSE)

            An = c(An, newElem)
        }

        idx.removed = sample(1:length(An), size = (K-1), replace = FALSE)
        An = An[-idx.removed]

        step.count = step.count + 1
        points[[step.count + 1]] = An
    }

    points
}
steps = 100
K = 3

x.coords = c(0)
for(i in 1:steps) {
    x.coords = c(x.coords, rep(i, i + 1))
}

An.list = simulate.An(steps, K)
An.flattened.vec = unlist(An.list, use.names = FALSE)

df = data.frame(
    step.coords = x.coords,
    points = An.flattened.vec
)

gif = ggplot( data = df ) +
    geom_point( mapping = aes( x = step.coords, y = points ), size = 0.5 ) +
    transition_manual(step.coords, cumulative = TRUE)

animate(gif, duration = 15)

ggplot( data = df ) +
    geom_point( mapping = aes( x = step.coords, y = points ), size = 0.5) +
    geom_line( mapping = aes( x = step.coords, y = rep( 0, length( step.coords ) ) ) )

Question 3

# Some constants which is require to be defined for ease of life
trial.count = 100
n = 1000

# Utility functions we shall need
G2 = function(An) {
    An.sorted = sort(An, decreasing = FALSE)
    An.gaplength = diff(An.sorted) - 1

    sum(An.gaplength >= 2)
}

L = function(An) {
    An.sorted = sort(An, decreasing = FALSE)
    An.gaplength = diff(An.sorted) - 1

    sum(An.gaplength)
}

results = replicate(trial.count, {
    An.list = simulate.An(n, 3)
    An.G2.list = sapply(An.list, G2)
    An.L.list = sapply(An.list, L)

    list("G2" = An.G2.list, "L" = An.L.list)
})

G2_n.sum.list = rep(0, n + 1)
L_n.sum.list = rep(0, n + 1)

print(results)
##    [,1]         [,2]         [,3]         [,4]         [,5]        
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,6]         [,7]         [,8]         [,9]         [,10]       
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,11]        [,12]        [,13]        [,14]        [,15]       
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,16]        [,17]        [,18]        [,19]        [,20]       
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,21]        [,22]        [,23]        [,24]        [,25]       
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,26]        [,27]        [,28]        [,29]        [,30]       
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,31]        [,32]        [,33]        [,34]        [,35]       
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,36]        [,37]        [,38]        [,39]        [,40]       
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,41]        [,42]        [,43]        [,44]        [,45]       
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,46]        [,47]        [,48]        [,49]        [,50]       
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,51]        [,52]        [,53]        [,54]        [,55]       
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,56]        [,57]        [,58]        [,59]        [,60]       
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,61]        [,62]        [,63]        [,64]        [,65]       
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,66]        [,67]        [,68]        [,69]        [,70]       
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,71]        [,72]        [,73]        [,74]        [,75]       
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,76]        [,77]        [,78]        [,79]        [,80]       
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,81]        [,82]        [,83]        [,84]        [,85]       
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,86]        [,87]        [,88]        [,89]        [,90]       
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,91]        [,92]        [,93]        [,94]        [,95]       
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
##    [,96]        [,97]        [,98]        [,99]        [,100]      
## G2 integer,1001 integer,1001 integer,1001 integer,1001 integer,1001
## L  numeric,1001 numeric,1001 numeric,1001 numeric,1001 numeric,1001
for(i in 1:trial.count) {
    G2 = results[1, i]$G2
    L = results[2, i]$L

    G2_n.sum.list = G2_n.sum.list + G2
    L_n.sum.list = L_n.sum.list + L
}

G2_n.sum.list = G2_n.sum.list / n
L_n.sum.list = L_n.sum.list / n

plot( 1:(n + 1), G2_n.sum.list, type = "l" )

plot( 1:(n + 1), L_n.sum.list, type = "l" )

Using \(Theorem 2.1.1\) given in the reference, we get the following result,

\[ \limsup_{n\to\infty} \frac{L(A_n)}{h_n} = \frac{K - 1}{K} \\ \implies L(A_n) = \Theta(h_n) \]

Now, since we’re estimating \(L(A_n)\) via \(L_n\), we can say that \(L_n = O(h_n)\) , since \(\Theta(h_n)\) represents the tightest bound, we can relax it slightly to get use \(O(h_n)\) instead.