Documentation

Dynamics.RandomWalk

Random-walk kernels on graphs #

Kernels on the vertices of a finite simple graph G with no isolated vertex (hd : ∀ v, 0 < G.degree v):

noncomputable def Dynamics.Kernel.uniformNeighbor {V : Type u_1} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (hd : ∀ (i : V), 0 < G.degree i) :

Uniform sampling among the neighbours: the simple random walk D⁻¹A on G.

Equations
Instances For
    theorem Dynamics.Kernel.uniformNeighbor_support {V : Type u_1} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (hd : ∀ (i : V), 0 < G.degree i) (i j : V) :
    0 < (uniformNeighbor G hd i).weight j ↔ G.Adj i j

    The simple random walk charges exactly the edges.

    theorem Dynamics.Kernel.uniformNeighbor_expect {V : Type u_1} [Fintype V] {G : SimpleGraph V} [DecidableRel G.Adj] (hd : ∀ (i : V), 0 < G.degree i) (x : V) (f : V → ℝ) :
    (uniformNeighbor G hd x).expect f = (∑ w ∈ G.neighborFinset x, f w) / ↑(G.degree x)

    Expectation under uniform neighbour sampling is the average over the neighbours.

    theorem Dynamics.Kernel.uniformNeighbor_expect_eq_avg {V : Type u_1} [Fintype V] {G : SimpleGraph V} [DecidableRel G.Adj] (hd : ∀ (i : V), 0 < G.degree i) (x : V) (f : V → ℝ) :
    (uniformNeighbor G hd x).expect f = avg fun (u : ↑(G.neighborSet x)) => f ↑u

    Expectation under uniform neighbour sampling is the uniform average avg over the neighbour set.

    noncomputable def Dynamics.Kernel.lazyNeighbor {V : Type u_1} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] [DecidableEq V] (hd : ∀ (i : V), 0 < G.degree i) :

    The lazy random walk (I + D⁻¹A)/2 on G: stay with probability 1/2, otherwise move to a uniformly random neighbour.

    Equations
    Instances For
      theorem Dynamics.Kernel.lazyNeighbor_weight {V : Type u_1} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] [DecidableEq V] (hd : ∀ (i : V), 0 < G.degree i) (i j : V) :
      (lazyNeighbor G hd i).weight j = ((if i = j then 1 else 0) + if G.Adj i j then (↑(G.degree i))⁻¹ else 0) / 2

      Entries of the lazy random walk: (I + D⁻¹A)/2.

      theorem Dynamics.Kernel.lazyNeighbor_expect {V : Type u_1} [Fintype V] {G : SimpleGraph V} [DecidableRel G.Adj] [DecidableEq V] (hd : ∀ (i : V), 0 < G.degree i) (x : V) (f : V → ℝ) :
      (lazyNeighbor G hd x).expect f = f x / 2 + (∑ w ∈ G.neighborFinset x, f w) / (2 * ↑(G.degree x))

      Expectation under the lazy random walk: half the current value plus half the neighbour average.