1 Classical Walks

Classical random walks are defined on a graph, with the walker being on some initial node $i_0$ with a probability $\lambda_i$, and “hopping” from node $i$ to $j$ in each time step with a probability given by $p_{ij}$. We can thus define a transition matrix $P := P_{ij} = p_{ij}$ which is row stochastic. Thus, the probability mass function of the walker at time step $t$ is given by $\lambda P^t$. Of course, the exact structure of the graph and the probabilities will decide the properties of the walk and there exists a vast amount of literature devoted to this analysis.

We however will restrict our discussion to the symmetric walk on the 1D chain. This is often called the 1D-Simple Symmetric Random Walk, and defined in the following way.

Definition

Consider an infinite 1 D chain (Figure 1.1), with nodes marked by $\mathbb{Z}$.

Figure 1.1: A schematic representation of the 1D Chain. Nodes are marked by integers, and edges exist only between neighbor nodes. The simple symmetric random walk is when the walker chooses to jump along either edge with equal probability.

Define the probability of hopping from node $i$ to node $j$

\[ p_{ij} = \begin{cases} 1/2 & |i - j| = 1 \\ 0 & \text{otherwise} \end{cases} \]

And the initial state as

\[ \lambda_{ij} = \begin{cases} 1 & i = 0 \\ 0 & \text{otherwise} \end{cases} \]

Thus, the hopper can only move to it nearest neighbors, starting from node 0.

Note that $P(X_t = i | \text{ HISTORY }) = P(X_t = i | X_{t-1})$, which means that the walk is a Markov chain.

Multiple Walkers

The SSRW is clearly a stochastic process, and each run of this process will lead to different paths being chosen by the walker, and we are my interested in what the walker does on an average rather than what happens in a particular instance. Thus, we can observe multiple walks, and plot their paths to visualize how they would spread in Figure 1.2.

In order to simulate a walk, we sample $X_i \in \{-1, 1\}$ with equal probability, and add it to the previous position $S_{i-1}$ to get $S_i$. Note $S_0 = 0$. Thus, this is equivalent to sampling from [1, -1] uniformly t times and performing a cumulative sum. For n walkers, we can sample (t, n) such random numbers, and do a cumulative sum along the first dimension.

bm = cumsum(rand([1, -1], (200, 15)), dims=1);

Figure 1.2: An ensemble of classical walkers. Since the walk is stochastic, different walkers have different trajectories.

Probability mass function

Another common way to visualize the walk is to plot the probability that the walker is on node $i$ at time $t$. For this, we define the transition matrix and $\lambda$ appropriately and find $\lambda P^t$. Note however that the transition matrix for the SSRW is Tridiagonal with the Upper and Lower diagonals as 0.5 and the diagonal as 0, and there exist efficient storage and multiplication routines. Also, since we can only store a finite matrix, we limit the walk to some size. At the boundaries, we set open conditions, because this is the easiest to implement. Therefore, the walk can be seen as an evolution of a probability distribution, and the way that the spread occurs can be seen in Figure 1.3.

cps, cps_t = let
    t = 21
    U = SymTridiagonal(fill(0., 31), fill(0.5, 30))
    λ = fill(0., 31)
    λ[16] = 1
    ps = accumulate(1:t, init=λ) do old, _
        U * old
    end[t÷3:t÷3:t], t÷3
end;

Figure 1.3: Probability distribution of a classical walker in time. Note the well known diffusive spread of the walk. Although the walker eventually scans the entire space, it is mostly concentrated around the origin, and spreads slowly($\sigma \propto \sqrt{t}$)

Properties of the walk

Certain properties of the walk that are interesting for the problem we pose in the subsequent sections. Primarily, we are interested in the mean, standard deviation and recurrence of the graph.

The probability that a walker is on node $n$ at time $t$ is given by the expression

\[p(n, t) = \binom{t}{\frac{t+n}{2}} \frac{1}{2^t}\]

This equation is valid only if $t + n$ is even and $n \le t$. If $t + n$ is odd or $n > t$, the probability is zero It should be obvious from the even symmetry of $p(n, t)$ that the mean $\mu(t) = \sum_n np(n,t) = 0$. This comes from the fact that the walk is symmetric. From Figure 1.3, we see that the walker spreads diffusively, and is more heavily concentrated in the middle of the chain rather than the edges. Mathematically, this follows from the binomial distribution.

The standard deviation of the walker position $\sigma(t) = \sqrt{\langle n^2 \rangle - \langle n\rangle^2} = \sqrt{\sum_n n^2p(n,t)} = \sqrt t$¹. Therefore, this means that the walker reaches about double the space in about four times the amount of steps.

# Classical Walks {#sec-classical} ```{julia} #| echo: false using Plots using Luxor using LinearAlgebra ``` Classical random walks are defined on a graph, with the walker being on some initial node $i_0$ with a probability $\lambda_i$, and "hopping" from node $i$ to $j$ in each time step with a probability given by $p_{ij}$. We can thus define a transition matrix $P := P_{ij} = p_{ij}$ which is row stochastic. Thus, the probability mass function of the walker at time step $t$ is given by $\lambda P^t$. Of course, the exact structure of the graph and the probabilities will decide the properties of the walk and there exists a vast amount of literature devoted to this analysis. We however will restrict our discussion to the symmetric walk on the 1D chain. This is often called the 1D-Simple Symmetric Random Walk, and defined in the following way. ## Definition Consider an infinite 1 D chain (@fig-onedchain), with nodes marked by $\mathbb{Z}$. ```{julia} #| echo: false #| label: fig-onedchain #| fig-cap: "A schematic representation of the 1D Chain. Nodes are marked by integers, and edges exist only between neighbor nodes. The simple symmetric random walk is when the walker chooses to jump along either edge with equal probability." let d = Drawing(800, 200) origin() for i in -5:4 setcolor("purple") arc2r(Point(i*60+30, -20), Point(i*60, -30), Point(i*60+60, -30), action=:stroke) setcolor("darkgreen") arc2r(Point(i*60+30, -40), Point(i*60+60, -30), Point(i*60, -30), action=:stroke) end setcolor("purple") arc2r(Point(-6*60+30, -20), Point(-6*60+30, -50), Point(-6*60+60, -30), action=:stroke) setcolor("darkgreen") arc2r(Point(-6*60+30, -40), Point(-6*60+60, -30), Point(-6*60+30, -20), action=:stroke) setcolor("purple") arc2r(Point(5*60+30, -20), Point(5*60, -30), Point(5*60+30, -50), action=:stroke) setcolor("darkgreen") arc2r(Point(5*60+30, -40), Point(5*60+30, -10), Point(5*60, -30), action=:stroke) setfont("Helvetica", 24) for i in -5:5 setcolor("#808080") settext("$(i)", Point(i*60, 20)) setcolor("red") circle(Point(i*60, -30), 10, action=:fill) end setcolor("brown") setfont("Helvetica", 16) settext("0.5", Point(20, -51)) settext("0.5", Point(20, -10)) finish() d end ``` Define the probability of hopping from node $i$ to node $j$ $$ p_{ij} = \begin{cases} 1/2 & |i - j| = 1 \\ 0 & \text{otherwise} \end{cases} $$ And the initial state as $$ \lambda_{ij} = \begin{cases} 1 & i = 0 \\ 0 & \text{otherwise} \end{cases} $$ Thus, the hopper can only move to it nearest neighbors, starting from node 0. Note that $P(X_t = i | \text{ HISTORY }) = P(X_t = i | X_{t-1})$, which means that the walk is a Markov chain. ## Multiple Walkers The SSRW is clearly a stochastic process, and each run of this process will lead to different paths being chosen by the walker, and we are my interested in what the walker does on an average rather than what happens in a particular instance. Thus, we can observe multiple walks, and plot their paths to visualize how they would spread in @fig-cwm. In order to simulate a walk, we sample $X_i \in \{-1, 1\}$ with equal probability, and add it to the previous position $S_{i-1}$ to get $S_i$. Note $S_0 = 0$. Thus, this is equivalent to sampling from `[1, -1]` uniformly `t` times and performing a cumulative sum. For `n` walkers, we can sample `(t, n)` such random numbers, and do a cumulative sum along the first dimension. ```{julia} bm = cumsum(rand([1, -1], (200, 15)), dims=1); ``` ```{julia} #| echo: false #| label: fig-cwm #| fig-cap: "An ensemble of classical walkers. Since the walk is stochastic, different walkers have different trajectories." Plots.plot(bm, xlabel="\$t\$", ylabel="\$n\$", label=reshape(map(i->"W $(i)", (1:15)), 1, :), legend=:outerright, ylims=(-40, 40)) ``` ## Probability mass function Another common way to visualize the walk is to plot the probability that the walker is on node $i$ at time $t$. For this, we define the transition matrix and $\lambda$ appropriately and find $\lambda P^t$. Note however that the transition matrix for the SSRW is Tridiagonal with the Upper and Lower diagonals as 0.5 and the diagonal as 0, and there exist efficient storage and multiplication routines. Also, since we can only store a finite matrix, we limit the walk to some size. At the boundaries, we set open conditions, because this is the easiest to implement. Therefore, the walk can be seen as an evolution of a probability distribution, and the way that the spread occurs can be seen in @fig-cwp. ```{julia} cps, cps_t = let t = 21 U = SymTridiagonal(fill(0., 31), fill(0.5, 30)) λ = fill(0., 31) λ[16] = 1 ps = accumulate(1:t, init=λ) do old, _ U * old end[t÷3:t÷3:t], t÷3 end; ``` ```{julia} #| echo: false #| label: fig-cwp #| fig-cap: "Probability distribution of a classical walker in time. Note the well known diffusive spread of the walk. Although the walker eventually scans the entire space, it is mostly concentrated around the origin, and spreads slowly($\\sigma \\propto \\sqrt{t}$)" Plots.plot(begin map(0:3) do i if i == 0 init = fill(0., 31) init[16] = 1 Plots.plot(-15:15, init, ylims=(0, 1), ylabel="\$P_t(n)\$", xlabel="\$n\$", title="\$t=$(i*cps_t)\$", legend=false) else Plots.plot(-15:15, cps[i], ylims=(0, 1), ylabel="\$P_t(n)\$", xlabel="\$n\$", title="\$t=$(i*cps_t)\$", legend=false) end end end...,) ``` ## Properties of the walk Certain properties of the walk that are interesting for the problem we pose in the subsequent sections. Primarily, we are interested in the mean, standard deviation and recurrence of the graph. The probability that a walker is on node $n$ at time $t$ is given by the expression $$p(n, t) = \binom{t}{\frac{t+n}{2}} \frac{1}{2^t}$$ This equation is valid only if $t + n$ is even and $n \le t$. If $t + n$ is odd or $n > t$, the probability is zero It should be obvious from the even symmetry of $p(n, t)$ that the mean $\mu(t) = \sum_n np(n,t) = 0$. This comes from the fact that the walk is symmetric. From @fig-cwp, we see that the walker spreads diffusively, and is more heavily concentrated in the middle of the chain rather than the edges. Mathematically, this follows from the binomial distribution. The standard deviation of the walker position $\sigma(t) = \sqrt{\langle n^2 \rangle - \langle n\rangle^2} = \sqrt{\sum_n n^2p(n,t)} = \sqrt t$ @portugal_quantum_2018. Therefore, this means that the walker reaches about double the space in about four times the amount of steps.