Proof of Proposition 3, pp. 20–21 — chaining u_{x_{i+1}} = u_{x_i}√(π_{x_{i+1}}/π_{x_i}) along paths gives u_y = u_{x_1}√(π_y/π_{x_1})
ProvedQuantumWalkSearch.SingularGap.path_chainingmarkov-chainsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1strongly-connected-graphs
Let be an irreducible Markov chain on a finite state space with stationary distribution , and let satisfy
that is, along every edge of the graph underlying the chain. Then for all ,
Chaining the edge relation along a path gives , and irreducibility (strong connectivity of the graph) supplies a path from to every . In particular is a scalar multiple of , which is how the proof of Proposition 3 concludes.
Formalization Note The graph underlying the chain has an edge exactly when (Mathlib's Matrix.toQuiver), and irreducibility is Mathlib's Matrix.IsIrreducible.
Preamble
import Mathlib import Definitions.Def_QuantumWalkSearch_SingularGap_Discriminant open Matrix
Formal statement
namespace QuantumWalkSearch.SingularGap
theorem path_chaining {X : Type*} [Fintype X] [DecidableEq X]
(P : Matrix X X ℝ) (π : X → ℝ)
(hP : P ∈ Matrix.rowStochastic ℝ X) (hirr : P.IsIrreducible)
(hπ : IsStationaryDistribution P π)
(u : X → ℂ)
(hu : ∀ x y : X, 0 < P x y → u y = u x * ((Real.sqrt (π y / π x) : ℝ) : ℂ)) :
∀ x₁ y : X, u y = u x₁ * ((Real.sqrt (π y / π x₁) : ℝ) : ℂ) := by sorry
end QuantumWalkSearch.SingularGap
Source
Magniez, Nayak, Roland, Santha, Search via Quantum Walk, arXiv:quant-ph/0608026v4, pp. 20-21, proof of Proposition 3 (path chaining)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.