Walker on a strip

46.2 μs

Assume the probability of the walker being on some x be denoted by an array called the state vector, denoted by $| ψ ⟩$

9.1 μs

Float641

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

more91

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

0.0

100

0.0

xxxxxxxxxx
 
ψ = zeros(Float64, 100); ψ[50] = 1; ψ

16.5 ms

Further, every step basically shifts around the probability. Assume that the probability of a particle jumping left is $p_{l}$ , jumping right is $p_{r}$ , staying is $p_{c} = 1 - p_{r} - p_{c}$ . Then, the probability of particle in x at t is

$ρ (x, t) = ρ (x - 1, t - 1) \cdot p_{r} + ρ (x + 1, t - 1) \cdot p_{l} + ρ (x, t - 1) \cdot p_{c}$

13.1 μs

Another way to look at this is to see influx and outflux.

$Δ ρ (x, t) = ρ (x - 1, t - 1) \cdot p_{r} + ρ (x + 1, t - 1) \cdot p_{l} - ρ (x, t - 1) \cdot p_{r} - ρ (x, t - 1) \cdot p_{l}$

$\begin{aligned} ρ (x, t) = & Δ ρ (x, t) + ρ (x, t - 1) \\ ρ (x, t) = & ρ (x - 1, t - 1) \cdot p_{r} + ρ (x + 1, t - 1) \cdot p_{l} \\ - ρ (x, t - 1) \cdot p_{r} - ρ (x, t - 1) \cdot p_{l} + ρ (x, t - 1) \\ = & ρ (x - 1, t - 1) \cdot p_{r} + ρ (x + 1, t - 1) \cdot p_{l} \\ + (1 - p_{r} - p_{l}) ρ (x, t - 1) \\ = & ρ (x - 1, t - 1) \cdot p_{r} + ρ (x + 1, t - 1) \cdot p_{l} + ρ (x, t - 1) \cdot p_{c} \end{aligned}$

9.0 μs

Now this dynamics has a very important property. It is memoryless. It doesn't matter how we got there, but the previous step determines the next. Mathematically, this means,

$M^{s + t} | ψ ⟩ = (M^{t} \circ M^{s}) | ψ ⟩$

such maps are called Markovian maps and they can be represented as a single matrix operation on the state vector.

4.9 ms

Explicitly, the matrix is $[\begin{matrix} p_{c} & p_{l} & . & . & \dots \\ p_{r} & p_{c} & p_{l} & . & \dots \\ . & p_{r} & p_{c} & p_{l} & \dots \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋱ \end{matrix}]$

8.1 μs

xxxxxxxxxx
 
using LinearAlgebra

10.1 ms

M (generic function with 1 method)

xxxxxxxxxx
 
M(pl, pr, n) = Tridiagonal(fill(pr, n-1), fill(1-pr-pl, n), fill(pl, n-1))

72.6 μs

5×5 Tridiagonal{Float64, Vector{Float64}}:
 0.8  0.1   ⋅    ⋅    ⋅ 
 0.1  0.8  0.1   ⋅    ⋅ 
  ⋅   0.1  0.8  0.1   ⋅ 
  ⋅    ⋅   0.1  0.8  0.1
  ⋅    ⋅    ⋅   0.1  0.8

xxxxxxxxxx
 
M(0.1, 0.1, 5)

5.0 μs

xxxxxxxxxx
 
using Plots

5.7 s

xxxxxxxxxx
 
let
    ψ = zeros(Float64, 100); ψ[50] = 1; ψ
    m = M(0.1, 0.1, 100)
    @gif for i in 1:100
        ψ .= m*ψ
        plot(-50:49, ψ, ylims=(0,1))
    end
end

18.5 s

x
 
let
    ψ = zeros(Float64, 99); ψ[50] = 100; ψ
    m = M(0.3, 0.3, 99)
    q = plot([0], [100], ylims=(0,120))
    a = @animate for i in 1:50
        ψ .= round.(m*ψ)
        p=plot(-49:49, ψ, ylims=(0,50))
        push!(q[1][1], sum(ψ))
        plot(p,q, layout=(2,1))
    end
    gif(a)
end

3.3 s

x
 
let
    ψ = zeros(Float64, 99); ψ[50] = 100; ψ
    m = M(0.1, 0.1, 99)
    q = plot([0], [100], ylims=(0,120))
    a = @animate for i in 1:50
        ψ .= round.(m*ψ)
        p=plot(-49:49, ψ, ylims=(0,50))
        push!(q[1][1], sum(ψ))
        plot(p,q, layout=(2,1))
    end
    gif(a)
end

3.5 s

x
 
let
    ψ = zeros(Float64, 99); ψ[[46,54]] .= 75; ψ
    m = M(0.3, 0.3, 99)
    q = plot([0], [150], ylims=(0,170))
    a = @animate for i in 1:100
        ψ .= round.(m*ψ)
        p=plot(-49:49, ψ, ylims=(0,50))
        push!(q[1][1], sum(ψ))
        plot(p,q, layout=(2,1))
    end
    gif(a)
end

6.2 s