Tuesday, May 06, 2008

Two Problems, One Mathematics (1 of 2)

"Besicovitch insists that I publish; the fact that I was able to forsee interesting mathematical results shows that there must be be something in the theory." -- Piero Sraffa (Diary entry, 31 May 1958)
1.0 Introduction
In this post, I derive the same equation for two completely different problems. One is an economics model. The other is a simplified presentation of how Google might automatically calculate page ranks to determine the order in which web pages are presented to a user on completion of his search. I could have complicated my exposition by considering a third problem: the steady state probability distribution in a Markov chain.

2.0 Prices for Simple Reproduction
Consider an economy in which n commodities are produced. Each commodity is produced in a process in which it is the only output. In other words, no joint production, such as of wool and mutton, occurs in this economy. n processes are in use, each producing one of the n commodities, and all commodities are produced by one of these processes. Each production process requires a year to complete and uses up all its inputs.

Let ai,j denote the quantity of the ith commodity used in the production of the jth commodity. Quantities are measured in normalized units, such that the output of each process is one unit of the respective commodity. The nxn matrix A is the Leontief input-output matrix of interindustry quantity flows for this economy. Each element of A is non-negative.

Assume that this economy is undergoing simple reproduction. That is, the output of each process is exactly equal to the total inputs of that commodity used across all processes. (If it helps, one might think of the inputs to each process as including the commodities consumed by the workers operating that process. Labor inputs are not shown in the representation of this economy being considered here.) Anyways, this assumption implies that the sum for each row in A is unity.

Suppose each process is operated by a separate firm. The firm own ats the end of each year a single (normalized) unit of a single commodity. For the firm to continue in operation, it must trade this commodity for an appropriate amount of each of its inputs in all-around markets. Let pT denote the row vector of the prices in these markets. The condition that the economy continue in operation implies the following equation for prices:
pT A = pT
This characterization of prices is a non-neoclassical idea. Markets have not been modeled here as including any sort of maximization process. Nor have these prices been presented as a (stable?) limit point of some sort of dynamic process. Sraffa describes these prices as follows:
"There is a unique set of exchange-values which if adopted by the market restores the original distribution of the products and makes it possible for the process to be repeated; such values spring directly from the methods of production." -- P. Sraffa (1960)
3.0 Google Page Ranks
I now consider a re-definition of all of my symbols. Suppose n web pages have been identified, perhaps by a web-crawler. We want to rank these pages in some way.

These web pages contain links, including to one another. In ranking them, perhaps a page in which a high proportion of the links on other pages goes to that page should have a high rank. But ratios of the proportion of links on other pages that go to that page should be weighted by the ranks of those other pages. These ideas can be formalized.

Let mi,j be the number of links on the ith web page to the jth web page, for i unequal to j. Let mi,i be zero. Let mi be the total number of links on the ith page, excluding links to itself and to pages outside the pages being ranked.
ai,j = mi,j/mi, i = 1, 2, ..., n; j = 1, 2, ..., n
I have now defined a nxn matrix A, where each element is the proportion of the links on a page within a web that go to another specified page in that web. Each element in A is non-negative, and each row adds up to unity. Also, the principal diagonal of A is zero, although that property is not used in the following mathematics.

Let pT denote the row vector of page ranks. Page ranks satisfy the following system of equations:
pT A = pT

In the next part, I consider conditions under which a solution exists and is unique.

5.0 References

No comments: