0:00

Okay, so now I want to take you through a quick proof of this convergence theorem.

Â And what we'll, you know, the proof is useful.

Â It's a proof that's not entirely insightful because its one that's going

Â to leverage a lot of results in, in mathematics and, a, not be directed to

Â constructive proof. you can do a direct constructive proof

Â which is a little bit more involved. And let me talk some of the intuitions

Â behind this before I go into the, the mathematical proof.

Â And you know one, one thing that's, that's true is, is you know, if you've

Â got periodicity. It's going to be easy to construct some

Â examples where things blink on and off so you won't get convergence.

Â So periodicity, aperiodicity is going to be necessary convergence, for

Â convergence. And then the idea is, with aperiodicity

Â one thing you can show is that then the matrix actually, eventually, is going to

Â be incorporating information from every other person.

Â And, and once you start doing that, then the idea is that effectively each

Â individual, you know, the person who has the lowest belief is always going to have

Â to be coming up over time, right? So they're weighting other beliefs and

Â indirectly weighting everybody and the person with the highest belief is going

Â to be dragged down over time. And so, those things are going to have to

Â come towards each and they're going to actually converge and so once you got a

Â periodicity. Then you get this reach, which will

Â eventually start dragging things towards each other and, eventually things will

Â converge. Now, what they converge to the fact that

Â that everybody is going to have to be moving towards the, the middle, means

Â that each row is going to have to actually converge to the same thing.

Â So everybody is going to have to have the same belief over time, and then whatever

Â that row of the t matrix raised to some power starts converging to it's going to

Â have to be the same thing for each individual.

Â And we'll see that, that in fact is going to have to be an eigenvector in

Â order for that to still be something which, when you multiply it by the

Â matrix, gives back the same belief. So, if we can converge to something, it's

Â going to have to be that those things are unit eigenvectors.

Â And so that's the sort of high level intuition behind that and we'll go

Â through the proof and, and you know, playing with these things over time and

Â there is a lot intuition behind these and you begin to see how they, how they

Â operate. Okay, so now a more formal proof so

Â remember the theorem said that if we the, if we're dealing with this strongly

Â connected trust matrix. and, we'll say this thing is convergent

Â if and only if it's aperiodic, and then moreover we also get convergence then, if

Â and only if the limit looks like the, each row is based on the eigenvector.

Â which is the left hand side unit eigenvector, that has eigenvalue 1.

Â Okay, so, what's a proof of this? first of all, let's say that a matrix is

Â primitive if when you raise it to a high enough power, eventually all the entries

Â are a 0. Okay?

Â So there'll be some time in which you've raised it to some power all entries are

Â nonzero. And then, if you just keep raising it to

Â powers once you've got all entries non zero and each row is only to one it's

Â going to stay positive forever after. So a matrix primitive, is primitive if

Â and only if you get to a positive entries after some time.

Â Okay so one thing that you can show, and, and there's a number of different ways

Â you can show this, and this goes back in your algebra quite a ways.

Â so Perkins '61 will give you one proof of this, but if you've got something

Â strongly connected and stochastic, then its a periodic of and only if its

Â primitive. So primitive is equivalent to a

Â periodicity here, basically, if its periodic, then things aren't going to

Â always be all entry zero. They can blink on and off, if they, if

Â it's aperiodic, then after some time period, basically all the entries are

Â going to become positive, and you end up with a primitive matrix.

Â Okay, so that's useful. And,the second part then says that and,

Â and you can see, see different sources on this, if you've got something which is

Â strongly connected and, and it's a primitive matrix.

Â So once we've gotten something that's primitive.

Â Then if we look at the limit of this thing and it's stochastic matrix, the

Â limit is going to look like the every entry each row is just eventually taking

Â on the values of this eigenvector s1 through sn.

Â Okay, so everybody is effectively, when we think about what the initial beliefs

Â were. The beliefs that times zero basically,

Â everybody is going to be taking the eigenvector and multiplying that times

Â those beliefs to get those beliefs. Okay.

Â And you can get that theorem out of Meyer.

Â So what this does is, say, if you've got aperiodicity, you get that that's

Â primitive in this setting. and then primitive gives you the left

Â hand side eigenvector as the convergence. So, strongly connected and aperiodic

Â implies convergence and the converse is going to come from showing that if we've

Â got t being strongly connected, stochastic, and convergent then it's

Â gotta be primitive. Okay?

Â So what we want to show then is this, just you know, making sure we get the,

Â this converse part. So, if, if we've got something strongly

Â connected and stochastic and convergent, then it has to be primitive.

Â So what we showed is aperiodicity, gives you primitive, gives you convergence and

Â the limit. Now, we want to show if it's convergent,

Â then it in fact, has to be primitive. Which in this world is equivalent to any

Â periodicity, and that completes the circle of the theorem.

Â Okay, so lets, a, lets look at convergence, so if you're getting

Â convergence. There's something that this matrix

Â eventually converges to, lets call it S. So practice S, big S matrix, which will

Â get converged to. So that means that S times T has to be

Â equal to the limit of T to the T times T, right?

Â If this is the limit and then we just multiply it times T one more time, that

Â will be the same limit. So, that has to be giving us back S.

Â 6:41

Okay? So, that tells us that S times Tt has to

Â be equal to S. Whatever this limit looks like, this

Â limited matrix has to actually look like a matrix full of eigenvectors, because,

Â when you're multiplying this matrix times T, it's going to give you back the same

Â matrix. So that tells us that every row of S,

Â when you take a row here, it's like a vector multiplying T, you're getting back

Â the same row. So every row of S is an I, a left-hand

Â side eigenvector, and in fact, it has eigenvalue 1, so we're not moving this S

Â up and down. It's coming back directly as S, so it's

Â scaled exactly with an eigenvalue of 1. So, if you have something like this then

Â the Perron-Frobenius theorem, an eigenvector of an irreducible,

Â nonnegative matrix is strictly positive, if and only if it's associated with its

Â largest eigenvalue. And this vector is unique in the case

Â where the matrix is primitive. Okay, so since S is all positive, we end

Â up with T being primitive. And then, when T is primitive then

Â Perron-Frobenius theorem tells us the eigenvector is unique, and so, all rows

Â of S are exactly the same s, which was the S that we were working with before,

Â which is the left-hand side unit eigenvector.

Â So, Perron-Frobenius tells us that we basically get a unique eigenvector, and

Â in, in this case, we're getting the, the one with the largest eigenvalue of 1.

Â okay, so that's wraps up the, the proof here.

Â what is, what do we learn from this? Basically, convergence equivalent to

Â aperiodicity, aperiodicity gives us primitive.

Â That also gives us the, the convergence, so we know exactly what we're converging

Â to, which is the, eigen, left-hand side eigenvalue.

Â nice thing is aperiodicity is very easy to satisfy in this world.

Â So as long as you just had one person rate him or him, herself, so if anybody

Â puts weight on themselves, then you've automatically got a cycle of length 1.

Â And, once you have a cycle of length 1, then the greatest common divisor of all

Â the cycles has to be 1, right? So as long as we've got strongly

Â connected aperiodicity, as long as anybody's putting weight on themselves,

Â you're, you're done. The only way you're going to end up with

Â with situations where we don't have convergence is that nobody puts weight on

Â themselves. And then, we have all cycles being

Â multiples of, of some cycle length of at least 2.

Â And so if we have, you know, just person 1 weighing themselves, or at least one,

Â one set of people that listen to each other plus one that involves a triple.

Â that would be enough to have a greatest common divisor of, of length 1.

Â So, it's going to be very easy to satisfy aperiodicity and generically, in some

Â sense, it's going to be the true case. Okay, so what did we find?

Â we've got you know, when there's a convergence and giving convergence

Â actually gives us a consensus. Everybody converges to the same thing.

Â that also told us a little bit about the influence, because we're getting this s

Â vector out. So, it's previewing a lot of what's going

Â to happen in influence. if you want to figure out the full

Â details of this, there's actually a paper by myself and Ben [UNKNOWN] in two

Â thousand and ten, which gives more general details on this kind of

Â convergence in this model. but we can ask now, then you know, who

Â has influence, what can we say about influence, when is the consensus

Â accurate, these kinds of things as well.

Â