The Setting
Terminal values in a convex set can be propagated towards a tree’s root by averaging over children and applying nonexpansive maps. The order of these operations matters when the maps are nonlinear. Path weights measure the contribution of each terminal value to changes in the root output.
Let be a real normed space and let . All norms below are the norm of .
The Claim
Definition 1. An ordered rooted tree is a sequence of nonempty finite ordered levels , indexed by , together with order-preserving surjections , called parent maps.✦ For positive integers , the levels have the form (1), and the root is the unique node of . (1) For , the ancestor map follows the parent maps down to level .✦ The descendants of at level are the nodes at level whose ancestor at level is , as in (2). (2)
A weighted rooted tree on is an assignment of a positive real weight to each child , normalized separately over the children of each parent by (3). (3)✦ The root path weight of is the product of the child weights along its path from the root, defined by (4). (4)✦
A nonexpansive tree evaluation on and a convex subset of is a family of selfmaps , one for each , satisfying the nonexpansiveness condition (5). (5) For terminal values , the weighted child average is the map given by (6). (6)✦ The root evaluation of terminal values is the point specified recursively by (7), with node maps applied only at levels strictly less than the terminal level. (7)✦
Theorem 1. Let be a weighted rooted tree on an ordered rooted tree . Its path weights satisfy (8) for every and (9) whenever and . (8)✦ (9)✦ Let be a nonexpansive tree evaluation on and a convex set . For terminal values , its sensitivity is bounded by (10). (10)✦
What Is Checked
The statements concern ordered trees with nonempty finite levels and surjective order-preserving parent maps, positive child weights normalized at each parent, and nonexpansive selfmaps of a convex subset of a real normed space. Weighted child averages and root evaluations of terminal values in also belong to .