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.

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.

6.4: Proof of Convergence Theorem (Optional/Advanced 10:25)

Social and Economic Networks: Models and Analysis

与讲师见面