Ex5 (this is super ugly but I don’t think it’s worth polishing and it does work. All important ideas are in the first third of the proof, the rest just inelegantly resolves the details.)
We define our metric space as (X,d) where X:=[0,1]d is the set of probability distributions, and d(x,y)=∑dj=1|xj−yj|. Let x,y∈X and let Δ:=x−y, then d(Ax,Ay) can be computed as
where the last step holds because multiplying a vector with the state-transition matrix leaves the sum of entries unchanged. (Reasonably easy to verify using that each column of A sums up to 1.)
If x≠y, then Δ has at least one negative entry and the inequality is strict. In that case, let k=argmaxi∈{1,...,d}δi and ℓ=argmini∈{1,...,d}δi. In particular, we have δk>0>δℓ. Note that, when two numbers a,b∈R have different sign, then |a+b|=||a|−|b|| and thus |a|+|b|−|a+b|=min(2|a|,2|b|). Therefore, the amount that gets canceled out is at least
Let a′ be the smallest entry in A, then we can lower-bound the above as
d∑i=1a′2min(|δk|,|δℓ|)=2a′dmin(|δk|,|δℓ|)
Wlog, let |δk|>|δℓ|. Let K be the sum of all postive entires of Δ, then ∑di=1|δi|=2K, so the term we want to lower-bound is 2a′dδℓ2K=a′dδℓK. The sum of the negative entries is −K, which means that the one with largest norm among them has norm at least 1d−1|K|. Thus, the relative decrease is at least a′dKd−1K=a′dd−1>a′
Then, d(x,y)−d(A(x),A(y))d(x,y)≥a′, hence d(A(x),A(y)d(x,y)≤1−a′. This proves that A is a contraction; apply Banach’s theorem.
Ex5 (this is super ugly but I don’t think it’s worth polishing and it does work. All important ideas are in the first third of the proof, the rest just inelegantly resolves the details.)
We define our metric space as (X,d) where X:=[0,1]d is the set of probability distributions, and d(x,y)=∑dj=1|xj−yj|. Let x,y∈X and let Δ:=x−y, then d(Ax,Ay) can be computed as
d∑i=1|(Ax−Ay)i|=d∑i=1|(AΔ)i|=d∑i=1|d∑k=1ak,iδk|≤d∑i=1d∑k=1|ai,kδk|=d∑i=1δi
where the last step holds because multiplying a vector with the state-transition matrix leaves the sum of entries unchanged. (Reasonably easy to verify using that each column of A sums up to 1.)
If x≠y, then Δ has at least one negative entry and the inequality is strict. In that case, let k=argmaxi∈{1,...,d}δi and ℓ=argmini∈{1,...,d}δi. In particular, we have δk>0>δℓ. Note that, when two numbers a,b∈R have different sign, then |a+b|=||a|−|b|| and thus |a|+|b|−|a+b|=min(2|a|,2|b|). Therefore, the amount that gets canceled out is at least
d∑i=1|ai,kδk|+|ai,ℓδℓ|−|ai,kδk+ai,ℓδℓ|=d∑i=12min(|ai,kδk|,|ai,ℓδℓ|)
Let a′ be the smallest entry in A, then we can lower-bound the above as
d∑i=1a′2min(|δk|,|δℓ|)=2a′dmin(|δk|,|δℓ|)
Wlog, let |δk|>|δℓ|. Let K be the sum of all postive entires of Δ, then ∑di=1|δi|=2K, so the term we want to lower-bound is 2a′dδℓ2K=a′dδℓK. The sum of the negative entries is −K, which means that the one with largest norm among them has norm at least 1d−1|K|. Thus, the relative decrease is at least a′dKd−1K=a′dd−1>a′
Then, d(x,y)−d(A(x),A(y))d(x,y)≥a′, hence d(A(x),A(y)d(x,y)≤1−a′. This proves that A is a contraction; apply Banach’s theorem.