Probability. Robert P. Dobrow

Чтение книги онлайн.

INTRODUCTION

      All theory, dear friend, is gray, but the golden tree of life springs ever green.

      —Johann Wolfgang von Goethe

      Probability began by first considering games of chance. But today, it has practical applications in areas as diverse as astronomy, economics, social networks, and zoology that enrich the theory and give the subject its unique appeal.

      In this book, we will flip coins, roll dice, and pick balls from urns, all the standard fare of a probability course. But we have also tried to make connections with real-life applications and illustrate the theory with examples that are current and engaging.

      You will see some of the following case studies again throughout the text. They are meant to whet your appetite for what is to come.

I.1 Walking the Web

      There are about one trillion websites on the Internet. When you google a phrase like “Can Chuck Norris divide by zero?,” a remarkable algorithm called PageRank searches these sites and returns a list ranked by importance and relevance, all in the blink of an eye. PageRank is the heart of the Google search engine. The algorithm assigns an “importance value” to each web page and gives it a rank to determine how useful it is.

PageRank is a significant accomplishment of mathematics and linear algebra. It can be understood using probability. Of use are probability concepts called Markov chains and random walks, explored in Chapter 11. Imagine a web surfer who starts at some web page and clicks on a link at random to find a new site. At each page, the surfer chooses from one of the available hypertext links equally at random. If there are two links, it is a coin toss, heads or tails, to decide which one to pick. If there are 100 links, each one has a 1% chance of being chosen. As the web surfer moves from page to random page, they are performing a random walk on the web.

      What is the PageRank of site ? Suppose the web surfer has been randomly walking the web for a very long time (infinitely long in theory). The probability that they visit site is precisely the PageRank of that site. Sites that have lots of incoming links will have a higher PageRank value than sites with fewer links.

      The PageRank algorithm is actually best understood as an assignment of probabilities to each site on the web. Such a list of numbers is called a probability distribution. And since it comes as the result of a theoretically infinitely long random walk, it is known as the limiting distribution of the random walk. Remarkably, the PageRank values for billions of websites can be computed quickly and in real time.

I.2 Benford's Law

      Turn to a random page in this book. Look in the middle of the page and point to the first number you see. Write down the first digit of that number.

You might think that such first digits are equally likely to be any integer from 1 to 9. But a remarkable probability rule known as Benford's law predicts that most of your first digits will be 1 or 2; the chances are almost 50%. The probabilities go down as the numbers get bigger, with the chance that the first digit is 9 being less than 5% (Fig. I.1).

Benford's law, also known as the “first-digit phenomenon,” was discovered over 100 years ago, but it has generated new interest in recent years. There are a huge number of datasets that exhibit Benford's law, including street addresses, populations of cities, stock prices, mathematical constants, birth rates, heights of mountains, and line items on tax returns. The last example, in particular, caught the eye of business Professor Mark Nigrini who showed that Benford's law can be used in forensic accounting and auditing as an indicator of fraud [2012].