Iteration Fixed Point Exercises

This is the third of three sets of fixed point ex­er­cises. The first post in this se­quence is here, giv­ing con­text.

Note: Ques­tions 1-5 form a co­her­ent se­quence and ques­tions 6-10 form a sep­a­rate co­her­ent se­quence. You can jump be­tween the se­quences.

1. Let be a com­plete met­ric space. A func­tion is called a con­trac­tion if there ex­ists a such that for all , . Show that if is a con­trac­tion, then for any , the se­quence con­verges. Show fur­ther that it con­verges ex­po­nen­tially quickly (i.e. the dis­tance be­tween the th term and the limit point is bounded above by for some )

2. (Banach con­trac­tion map­ping the­o­rem) Show that if is a com­plete met­ric space and is a con­trac­tion, then has a unique fixed point.

3. If we only re­quire that for all , then we say is a weak con­trac­tion. Find a com­plete met­ric space and a weak con­trac­tion with no fixed points.

4. A func­tion is con­vex if , for all and . A func­tion is strongly con­vex if you can sub­tract a pos­i­tive para­baloid from it and it is still con­vex. (i.e. is strongly con­vex if is con­vex for some .) Let be a strongly con­vex smooth func­tion from to , and sup­pose that the mag­ni­tude of the sec­ond deriva­tive is bounded. Show that there ex­ists an such that the func­tion given by is a con­trac­tion. Con­clude that gra­di­ent de­scent with a suffi­ciently small con­stant step size con­verges ex­po­nen­tially quickly on a strongly con­vex smooth func­tion.

5. A finite sta­tion­ary Markov chain is a finite set of states, along with prob­a­bil­is­tic rule for tran­si­tion­ing be­tween the states, where rep­re­sents the space of prob­a­bil­ity dis­tri­bu­tions on . Note that the tran­si­tion rule has no mem­ory, and de­pends only on the pre­vi­ous state. If for any pair of states , the prob­a­bil­ity of pass­ing from to in one step is pos­i­tive, then the Markov chain is er­godic. Given an er­godic finite sta­tion­ary Markov chain, use the Banach con­trac­tion map­ping the­o­rem to show that there is a unique dis­tri­bu­tion over states which is fixed un­der ap­pli­ca­tion of tran­si­tion rule. Show that, start­ing from any state , the limit dis­tri­bu­tion ex­ists and is equal to the sta­tion­ary dis­tri­bu­tion.

6. A func­tion from a par­tially or­dered set to an­other par­tially or­dered set is called mono­tonic if im­plies that . Given a par­tially or­dered set with finitely many el­e­ments, and a mono­tonic func­tion from to it­self, show that if or , then is a fixed point of for all .

7. A com­plete lat­tice is a par­tially or­dered set in which each sub­set of el­e­ments has a least up­per bound and great­est lower bound. Un­der the same hy­pothe­ses as the pre­vi­ous ex­er­cise, ex­tend the no­tion of for nat­u­ral num­bers to for or­di­nals , and show that is a fixed point of for all with or and all ( means there is an in­jec­tion from to , and means there is no such in­jec­tion).

8. (Knaster-Tarski fixed point the­o­rem) Show that the set of fixed points of a mono­tonic func­tion on a com­plete lat­tice them­selves form a com­plete lat­tice. (Note that since the empty set is always a sub­set, a com­plete lat­tice must be nonempty.)

9. Show that for any set , forms a com­plete lat­tice, and that any in­jec­tive func­tion from to defines a mono­tonic func­tion from to . Given in­jec­tions and , con­struct a sub­set of and a sub­set of of such that and .

10. (Can­tor–Schröder–Bern­stein the­o­rem) Given sets and , show that if and , then . ( means there is an in­jec­tion from to , and means there is a bi­jec­tion)

Please use the spoilers fea­ture—the sym­bol ‘>’ fol­lowed by ‘!’ fol­lowed by space -in your com­ments to hide all solu­tions, par­tial solu­tions, and other dis­cus­sions of the math. The com­ments will be mod­er­ated strictly to hide spoilers!

I recom­mend putting all the ob­ject level points in spoilers and in­clud­ing meta­data out­side of the spoilers, like so: “I think I’ve solved prob­lem #5, here’s my solu­tion <spoilers>” or “I’d like help with prob­lem #3, here’s what I un­der­stand <spoilers>” so that peo­ple can choose what to read.

To­mor­row’s AI Align­ment Fo­rum Se­quences post will be “Ap­proval-di­rected agents: overview” by Paul Chris­ti­ano in the se­quence Iter­ated Am­plifi­ca­tion.

The next post in this se­quence will be re­leased on Satur­day 24th Novem­ber, and will be ‘Fixed Point Dis­cus­sion’.

• Ex 6:

If at any point , then we’re done. So as­sume that we get a strict in­crease each time up to . Since there are only el­e­ments in the en­tire poset, and is mono­tone, has to equal .

Ex 7:

For a limit or­di­nal , define as the least up­per bound of for all . If , then the set for is a set of size that maps into a set of size by tak­ing the value of the el­e­ment. Since there are no in­jec­tions be­tween these sets, there must be two or­di­nals such that. Since is mono­tone, that im­plies that for ev­ery or­di­nal , and thus is a fixed point. Since this proves the ex­er­cise.

Ex 8:

Start­ing from , we can cre­ate a fixed point via iter­a­tion by tak­ing , and iter­at­ing times as demon­strated in Ex 7. Call this fixed point . Sup­pose there was a fixed point such that and . Then at some point , but , which breaks the mono­ton­ic­ity of un­less . So gen­er­ated this way is always the small­est fixed point greater than .

Say we have fixed points . Then let be the least up­per bound of , and gen­er­ate a fixed point from . So will be greater than each el­e­ment of since is mono­tone, and is the small­est such fixed point as shown in the above para­graph. So the poset of fixed points is semi-com­plete with up­per bounds.

Now take our fixed points again. Now let be the great­est lower bound of , and gen­er­ate a fixed point . Since and is mono­tonic, , and so is a lower bound of . It has to be the great­est such bound be­cause it­self is already the great­est such bound in our poset, and is mono­tonic.

Thus the lat­tice of fixed points has all least up­per bounds and all great­est lower bounds, and is thus com­plete!

• #3:

on short­ens all dis­tances but is strictly mono­tonic.

#6: (the “show that if” con­di­tion fol­lows from the prop­erty, the ques­tion is likely mis­stated)

The iter­a­tion is so long that it must visit an el­e­ment twice. We can’t have a cy­cle in the or­der so the rep­e­ti­tion must be im­me­di­ate.

• Thanks, I ac­tu­ally wanted to get rid of the ear­lier con­di­tion that for all , and I did that.

• An­swer to ques­tion 1.

Let for ar­bi­trary . Call . Then by in­duc­tion () (power se­ries sim­plifi­ca­tion)

There­fore ie is a cauchy se­quence. How­ever is said to be com­plete, which by defi­ni­tion means any cauchy se­quence is con­ver­gent. So and So con­verges ex­po­nen­tially quickly

An­swer to ques­tion 2.

From part 1, as is con­tin­u­ous, So is a fixed point. Sup­pose and are both fixed points of a con­trac­tion map. Then and so there­fore so . Thus has a unique fixed point.

An­swer to ques­tion 3.

is a met­ric space. Its the real line with nor­mal dis­tance. Let . Then is a con­trac­tion map be­cause is differ­en­tiable and has the prop­erty . How­ever no fixed point ex­ists as . This works be­cause the se­quence gen­er­ated from re­peated ap­pli­ca­tions of will tend to in­finity, de­spite suc­ces­sive terms be­com­ing ever closer.

• For Q2, I be­lieve you aren’t done:

You have es­tab­lished that there is at most one fixed point, but not that a fixed point ex­ists.

• #6:

As­sume WLOG Then by mono­ton­ic­ity, we have If this chain were all strictly greater, than we would have istinct el­e­ments. Thus there must be some uch that By in­duc­tion, or all

#7:

As­sume nd con­struct a chain similarly to (6), in­dexed by el­e­ments of If all in­equal­ities were strict, we would have an in­jec­tion from o L.

#8:

Let F be the set of fixed points. Any sub­set S of F must have a least up­per bound n L. If x is a fixed point, done. Other­wise, con­sider which must be a fixed point by (7). For any q in S, we have Thus s an up­per bound of S in F. To see that it is the least up­per bound, as­sume we have some other up­per bound b of S in F. Then

To get the lower bound, note that we can flip the in­equal­ities in L and still have a com­plete lat­tice.

#9:

P(A) clearly forms a lat­tice where the up­per bound of any set of sub­sets is their union, and the lower bound is the in­ter­sec­tion.

To see that in­jec­tions are mono­tonic, as­sume nd s an in­jec­tion. For any func­tion, If nd that im­plies or some which is im­pos­si­ble since s in­jec­tive. Thus s (strictly) mono­tonic.

Now s an in­jec­tion Let e the set of all points not in the image of and let ote that since no el­e­ment of s in the image of Then On one hand, ev­ery el­e­ment of A not con­tained in s in y con­struc­tion, so On the other, clearly so QED.

#10:

We form two bi­jec­tions us­ing the sets from (9), one be­tween A’ and B’, the other be­tween A—A’ and B—B’.

Any in­jec­tion is a bi­jec­tion be­tween its do­main and image. Since nd s an in­jec­tion, s a bi­jec­tion where we can as­sign each el­e­ment o the uch that Similarly, s a bi­jec­tion be­tween nd Com­bin­ing them, we get a bi­jec­tion on the full sets.

• Q1

We wish to show that the terms of form a Cauchy se­quence, which suffices to demon­strate they con­verge in a com­plete space. Take , and WLOG . Then we know from the defi­ni­tion of con­trac­tion that . This con­verges to 0 as m in­creases, so the se­quence is Cauchy.

It’s easy to see that this makes the rate of con­ver­gence be­tween terms of the Cauchy se­quence ex­po­nen­tially quick. In­tu­itively that seems like it ought to make the se­quence con­verge to its limit with the same speed, but I don’t think that can be made rigor­ous with­out more steps.

Q2

Take a se­quence . This con­verges to some . Sup­pose was not a fixed point. Then choose an . A se­quence which con­verges to a limit has, for ev­ery , some such that . Then we know that but , con­tra­dict­ing the con­trac­tion con­di­tion. So there is at least one fixed point, .

Sup­pose there are two fixed points, , for dis­tinct and . If so, , which again con­tra­dicts the con­trac­tion con­di­tion. So there is at most one fixed point.

Q3

Take as the space , with the usual met­ric. Define . This is a weak con­trac­tion (to­ward in­finity) and has no fixed points within this space.