What makes WiFi faster at home than at a coffee shop? How does Google order its search results from the trillions of webpages on the Internet? Why does Verizon charge $15 for every GB of data we use? Is it really true that we are connected in six social steps or less? These are just a few of the many intriguing questions we can ask about the social and technical networks that form integral parts of our daily lives. This course is about exploring the answers, using a language that anyone can understand. We will focus on fundamental principles like “sharing is hard”, “crowds are wise”, and “network of networks” that have guided the design and sustainability of today’s networks, and summarize the theories behind everything from the social connections we make on platforms like Facebook to the technology upon which these websites run. Unlike other networking courses, the mathematics included here are no more complicated than adding and multiplying numbers. While mathematical details are necessary to fully specify the algorithms and systems we investigate, they are not required to understand the main ideas. We use illustrations, analogies, and anecdotes about networks as pedagogical tools in lieu of detailed equations. Please note that per Princeton University policy, no certificates, credentials or reports are awarded in connection with this course.
Analyzing Cascades: Part II
Loading...
From the course by Princeton University
Networks Illustrated: Principles without Calculus
31 ratings
Princeton University
Networks Illustrated: Principles without Calculus
31 ratings
From the lesson
Viral Videos on YouTube
What does it take for a video to become "viral" on YouTube? In this lesson, we will take a look at some of the key factors and models that have been used to explain this phenomenon. At the core is the notion of information cascade in a network, which is the counterpart to the wisdom of crowds.
Meet the Instructors
Christopher BrintonVisiting Researcher and Lecturer
Department of Electrical Engineering
Mung ChiangProfessor
Electrical Engineering
So what we just illustrated were the probabilities of no cascade, correct cascade, and incorrect cascade after the first pair for a certain chance that each private signal was correct. So we had been using 80% for that chance before, and we went through those computations. What we are showing here is a graph of how each of these three probabilities changes as the probability of being shown the true correct value varies, right? So, intuitively if we look at the black line which is the probability of having correct cascade. As this probability increases, all right. So as the probability being shown goes from 80 to 85%, 90%, 95. Even to 100%. The probability of having a correct cascade is going to go up.
of seeing a 1 or whatever the true value is. If the true value is a 0 by the way, this analysis will be exactly the same, right? So, we have a higher chance as the probability increases at the first two private signals are going to be showing 1. And also, the higher chance that the first power signal is going to be a 1 and that the flip will turn at 1. The flip probability never changes, but you have a higher chance of going into that case, so to speak. So, at the same time, we see that the probability of having an incorrect cascade is going to drop, because we have less chance of seeing a 0.
So and then in terms of having no cascade, having no cascade is going to be the highest when the probability is 50% because that's the highest chance that we're going to have two different private signals to start with, right. But then that also drops more because then we're, as we have more and more higher of a probability we're either going to be in a correct or an incorrect cascade. So just to summarize what we've just said and put it on the slides here, as the probability of showing the true value increases the probability of having no cascade is going to drop to 0%. The probability of having incorrect cascade is also going to drop to 0%. And all the probability is going to be
concentrated in having a correct cascade which is going to rise to 100%. And also notice that if you take any cross section here so if you look at any one of these given probabilities and you add up these values, they're all going to add to 100% all the time. So, for any one of these, these probabilities are going to add up to 100%. And, by the way, you're definitely encouraged to try out some of these computations and see whether what you get agrees with what's shown on the graph here by varying what this probability is. We just illustrated the one before for 80%.
So the graph that we just looked at showed us different probabilities after the first pair of people have guessed the true number. But what happens after the second, third and future pairs go?
What we want to ask is what is going to be the probability of having no cascade, after two pairs, five pairs or 50 pairs even. And we'll see how this probability is going to change. Make the same assumption as before here, that's the probability of seeing the true number is going to be 80%. So, it was also like interesting though, because we saw that if there is no cascade after a given pair, then the next pair is basically going to just be a repetition. Right? So, that the third person is going to be the same as the first person given that there was no cascade, right? So, after the first pair of people go, one and two, if there's no cascade here, then they're going to go again and it's basically going to be the same thing again. They're in the same shoes as person one and two. So, what we really need to happen, is we just need to have a sequence of events where there's just no cascades after two pairs. So, we already found the probability of having no cascade after one pair of being .16, before.
And the probability of having no cascade after the second pair is the same as the probability of having no cascade after the first pair,
it's just again, another 0.16. But the probability of both of these events happening is going to multiply them because we need them both to happen. So for two pairs we have .16 times .16, which is 0.0256, or about 2.56%. So that's a pretty small chance. So we're going to be in some cascade after the two pairs most likely with actually over 97% chance. Now for five pairs we have to take, again, the same thing we now instead of having just two of these we need to have five of them happen in a row. So we have .16 times .16 times .16, times .16, times .16. And that is equal to 0.000105. Which is less than one hundredth of a percent. So it's less than one one hundredth of a percent. So that's a very very small number. So now, even when we go to 50 pairs, you'd have to do the multiplication of .16 50 times and what that's going to have is, it's going to be a decimal probability with 37 zeros. So there's a 37 zeros before the first significant digit, whatever that is. So very, very basically impossible, almost impossible to happen. So it's almost impossible not to have a cascade after 50 pairs, that's what that's saying. Basically, what we're saying is that we're guaranteed to have a cascade eventually. The question is though, is this a good thing? And the answer is not necessarily because remember the cascade could either be correct or incorrect. What we have shown here is the probability of having nailed cascade goes to 0. Therefore the remaining probability has to be concentrated in whether it's a correct or incorrect cascade.
So what this graph here shows is it's shown again as we vary the probability of showing the correct value which we did at 80% before. And this is showing also the different, after a different number of pairs. So this applies what we saw before for having just one pair. This is for having two pairs, this is for having five pairs then 100 pairs and so forth. And this is just looking at the probability of a correct cascade, we're not showing the incorrect of no cascade here. But what we see first is obviously again that as the probability increases in anyone of this cases you're going to have a higher chance of having a correct cascade. But what's important to realize is that after the first two, maybe,
of having correct cascades, so even at 80%, this jumps a little bit from wherever we are, 72% to something a little over 80% of having correct cascade. Then it quickly saturates, right, so as we increase the number, that's what you should think of. And going up this way is increasing the number of pairs.
It quickly saturates in between five pairs and 100 pairs, there's really no difference. So still you see it increases though. What you have to realize is that the probability of having no cascade is dropping so much, right? Because we saw already that if we're 80%, this was going to be down to, essentially, 0 by the time we were at even five pairs. There's going to be basically nothing. The two pairs would be really low. So what that means is that all the remaining probability that's not in the correct cascade has to be concentrated in the chance of having an incorrect cascade. So as the number of pairs increases the probability of having a correct cascade is going to increase slightly but quickly saturate. The probability of having an incorrect cascade is also going to go up. It's going to be basically the exact mirror image of these lines, for a very high number of pairs. Once we have enough pairs, we can basically start to ignore the probability of having no cascade and assume it's going to be some cascade, so for very high values this is basically just going to be the exact mirror image. And this would be the probability of having an incorrect cascade.
So as we said NumPairs here, the number of pairs that we have, is increasing the chance of having incorrect cascade. And that's also pretty alarming because now we know that there's still a significant chance that we could have an incorrect cascade. Now this is somewhat counterintuitive, right? Because when the number of pairs is large we would expect a large amount of information to be available because we have more public actions. And therefore we would expect that a correct cascade should happen with a high probability. But what's happening here is that the cascades are blocking the aggregation of independent information. Which was so important to us when we were talking about the wisdom of crowds. Once we get a pair that displaced two zeros, we're going to be stuck with 0 forever, because people will trust the crowd's guess over their own. So all it takes is as we said, an odd person followed by an even person to show 0. And then we're going to have an incorrect cascade. That's it. So really in order to have a correct cascade we can't rely on having more information. We have to just hope that the moderator has chosen a very high chance of showing the correct value to everyone. And the reason for that is that as the probability of being shown the true number increases, the probability of having an incorrect cascade is going to drop and the probability of having a correct cascade is going to increase as we show before. Well, that's the only way to make that drop happen. Now, changing the number pairs isn't going to drastically increase the probability of having a correct cascade. As one final point, note that we did not compute the correct and incorrect cascade probabilities for multiple pairs. So we didn't run through those complications. We only did it for the probably of having no cascade. And the reason we didn't do that is because they're not as simple as just multiplying repeatedly like in the case that we know cascade. But even though the math is beyond us, explaining the key points doesn't require it because we just went through basically the key takeaways.
Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.
© 2017 Coursera Inc. All rights reserved.
