Eq. (17) — target dependency chain δ̃_{•,t}((s_1,…,s_k)) = δ_{•,t}(s_1)·∏_{i=2}^{k} δ_{s_{i−1},t}(s_i)
ProvedRoutingBC.Chaining.target_dependency_chainLet be a loop-free, source-oblivious routing scheme on a finite node set (total forwarding probability one at every non-target node, silent target), a traffic matrix, a target and with . Write and for the target dependencies. Then
The expected number of packets targeted at that pass through the whole sequence is thus the target dependency of its first node times a chain of pairwise dependencies, which no longer involves the sources.
Formalization Note. The page prints the product as ; is a misprint for , and the index would refer to a nonexistent , so the product over (the consecutive pairs of ) is stated. The sum over sources includes , which Lemma 1 excludes; the identity is claimed for every source, with no assumption on . No sign condition on is assumed.
import Mathlib import Definitions.Def_RoutingBC_Chaining_Routing
namespace RoutingBC.Chaining
theorem target_dependency_chain {V : Type*} [Fintype V] [DecidableEq V]
(R : V → V → V → V → ℝ) (hR : IsRoutingScheme R) (hobl : IsSourceOblivious R)
(T : V → V → ℝ) (t s₁ : V) (rest : List V) :
targetSeqDelta R T t (s₁ :: rest) =
targetDelta R T t s₁ *
(((s₁ :: rest).zip rest).map (fun ab => delta R ab.1 t ab.2)).prod := by sorry
end RoutingBC.Chaining
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.