André Nies
- Published in print:
- 2009
- Published Online:
- May 2009
- ISBN:
- 9780199230761
- eISBN:
- 9780191710988
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199230761.003.0005
- Subject:
- Mathematics, Logic / Computer Science / Mathematical Philosophy
This chapter shows the equivalence of K-triviality and lowness for Martin–Löf randomness. This coincidence extends to other lowness properties, such as being a base for Martin–Löf randomness, and ...
More
This chapter shows the equivalence of K-triviality and lowness for Martin–Löf randomness. This coincidence extends to other lowness properties, such as being a base for Martin–Löf randomness, and lowness for weak 2-randomness. To prove the results, the chapter develops the accounting, cost function and decanter methods, and the golden run construction. The Main Lemma, derived from the golden run construction, yields a general way to restrict K-trivial sets.Less
This chapter shows the equivalence of K-triviality and lowness for Martin–Löf randomness. This coincidence extends to other lowness properties, such as being a base for Martin–Löf randomness, and lowness for weak 2-randomness. To prove the results, the chapter develops the accounting, cost function and decanter methods, and the golden run construction. The Main Lemma, derived from the golden run construction, yields a general way to restrict K-trivial sets.
André Nies
- Published in print:
- 2009
- Published Online:
- May 2009
- ISBN:
- 9780199230761
- eISBN:
- 9780191710988
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199230761.003.0008
- Subject:
- Mathematics, Logic / Computer Science / Mathematical Philosophy
This chapter studies lowness properties of sets not necessarily below the halting problem. The main new notions are all related to traceability. It characterizes lowness for Schnorr, and computable ...
More
This chapter studies lowness properties of sets not necessarily below the halting problem. The main new notions are all related to traceability. It characterizes lowness for Schnorr, and computable randomness. It also studies strong jump traceability and its relationship to the cost function method of Chapter 5. Many research problems are posed.Less
This chapter studies lowness properties of sets not necessarily below the halting problem. The main new notions are all related to traceability. It characterizes lowness for Schnorr, and computable randomness. It also studies strong jump traceability and its relationship to the cost function method of Chapter 5. Many research problems are posed.
W. M. Gorman
C. Blackorby and A. F. Shorrocks (eds)
- Published in print:
- 1996
- Published Online:
- November 2003
- ISBN:
- 9780198285212
- eISBN:
- 9780191596322
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/0198285213.003.0017
- Subject:
- Economics and Finance, Microeconomics
This short note, published in Metroeconomica 13 (1961), begins with the assumption that the preferences of the consumer exhibit linear Engel curves, which were shown in ’Community preference fields’ ...
More
This short note, published in Metroeconomica 13 (1961), begins with the assumption that the preferences of the consumer exhibit linear Engel curves, which were shown in ’Community preference fields’ (Ch. 15) to be necessary for the existence of a community indifference map. Engel curves are curves showing the relationship between income level and spending on the consumption of some good, at a given price, and linear Engel curves crop up in several branches of economics. The note explores some of the properties of the preference fields in which linear Engel curves arise, and, in particular, of those in which the marginal propensity to consume each good is an absolute constant. The preference fields are characterized by closed‐form representations in terms of both the indirect utility function and the cost function. An application to international trade theory is discussed.Less
This short note, published in Metroeconomica 13 (1961), begins with the assumption that the preferences of the consumer exhibit linear Engel curves, which were shown in ’Community preference fields’ (Ch. 15) to be necessary for the existence of a community indifference map. Engel curves are curves showing the relationship between income level and spending on the consumption of some good, at a given price, and linear Engel curves crop up in several branches of economics. The note explores some of the properties of the preference fields in which linear Engel curves arise, and, in particular, of those in which the marginal propensity to consume each good is an absolute constant. The preference fields are characterized by closed‐form representations in terms of both the indirect utility function and the cost function. An application to international trade theory is discussed.
W. M. Gorman
C. Blackorby and A. F. Shorrocks (eds)
- Published in print:
- 1996
- Published Online:
- November 2003
- ISBN:
- 9780198285212
- eISBN:
- 9780191596322
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/0198285213.003.0007
- Subject:
- Economics and Finance, Microeconomics
This paper is from an unpublished typescript prepared at the University of North Carolina in 1970. It is a thorough analysis of the distance function that Gorman first discovered in ’Consumer budgets ...
More
This paper is from an unpublished typescript prepared at the University of North Carolina in 1970. It is a thorough analysis of the distance function that Gorman first discovered in ’Consumer budgets and price indices’ (Ch. 5), where it was used to recover the form of the direct preferences from a dual representation. In this paper, it stands on its own and is shown to be the natural dual of the cost or expenditure function; natural in this context means that the distance function has the same properties in quantities as the cost function has in prices.Less
This paper is from an unpublished typescript prepared at the University of North Carolina in 1970. It is a thorough analysis of the distance function that Gorman first discovered in ’Consumer budgets and price indices’ (Ch. 5), where it was used to recover the form of the direct preferences from a dual representation. In this paper, it stands on its own and is shown to be the natural dual of the cost or expenditure function; natural in this context means that the distance function has the same properties in quantities as the cost function has in prices.
Hidetoshi Nishimori
- Published in print:
- 2001
- Published Online:
- January 2010
- ISBN:
- 9780198509417
- eISBN:
- 9780191709081
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198509417.003.0009
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
A decision-making problem is often formulated as the minimization or maximization of a multivariable function, an optimization problem. This chapter shows that the methods of statistical mechanics ...
More
A decision-making problem is often formulated as the minimization or maximization of a multivariable function, an optimization problem. This chapter shows that the methods of statistical mechanics are useful to study some types of optimization problems including the number partitioning, the graph partitioning, the knapsack problem, and the satisfiability problem. All these problems are shown to be formulated and solved using the theory of spin glasses, in particular the replica method. Then, discussions are continued on the mathematical properties of simulated annealing, an approximate numerical method for generic optimization problems.Less
A decision-making problem is often formulated as the minimization or maximization of a multivariable function, an optimization problem. This chapter shows that the methods of statistical mechanics are useful to study some types of optimization problems including the number partitioning, the graph partitioning, the knapsack problem, and the satisfiability problem. All these problems are shown to be formulated and solved using the theory of spin glasses, in particular the replica method. Then, discussions are continued on the mathematical properties of simulated annealing, an approximate numerical method for generic optimization problems.
W. M. Gorman
C. Blackorby and A. F. Shorrocks (eds)
- Published in print:
- 1996
- Published Online:
- November 2003
- ISBN:
- 9780198285212
- eISBN:
- 9780191596322
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/0198285213.003.0006
- Subject:
- Economics and Finance, Microeconomics
Although this paper, which was published in Econometrica 32 (1964) can be read as a straightforward budgeting argument, it was inspired by a claim of Sargan's about the necessary and sufficient ...
More
Although this paper, which was published in Econometrica 32 (1964) can be read as a straightforward budgeting argument, it was inspired by a claim of Sargan's about the necessary and sufficient conditions for Friedman's permanent income hypothesis to be valid. A version of this hypothesis shows that a 10% increase in permanent income leads to a 10% increase in expenditure in every period. Sargan (1957) claimed that this would lead to a 10% increase in expenditure on every commodity. Section 2 of the paper disposes of the Sargan claim by means of a counter‐example, and Sect. 3 presents the restrictions on the cost function that are both necessary and sufficient for Friedman's permanent income hypothesis to hold. The remaining sections apply the solution derived and its special cases to problems of decentralized decision‐making suggested by Strotz and Samuelson, and to a problem discussed by Drèze.Less
Although this paper, which was published in Econometrica 32 (1964) can be read as a straightforward budgeting argument, it was inspired by a claim of Sargan's about the necessary and sufficient conditions for Friedman's permanent income hypothesis to be valid. A version of this hypothesis shows that a 10% increase in permanent income leads to a 10% increase in expenditure in every period. Sargan (1957) claimed that this would lead to a 10% increase in expenditure on every commodity. Section 2 of the paper disposes of the Sargan claim by means of a counter‐example, and Sect. 3 presents the restrictions on the cost function that are both necessary and sufficient for Friedman's permanent income hypothesis to hold. The remaining sections apply the solution derived and its special cases to problems of decentralized decision‐making suggested by Strotz and Samuelson, and to a problem discussed by Drèze.
Sergey N. Dorogovtsev
- Published in print:
- 2010
- Published Online:
- May 2010
- ISBN:
- 9780199548927
- eISBN:
- 9780191720574
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199548927.003.0014
- Subject:
- Physics, Theoretical, Computational, and Statistical Physics
This chapter demonstrates how a universal requirement for optimality leads to the complex structural organization of a network. It discusses a long-lasting criticism of the preferential concept and ...
More
This chapter demonstrates how a universal requirement for optimality leads to the complex structural organization of a network. It discusses a long-lasting criticism of the preferential concept and describes existing approaches to the optimization-driven evolution of complex networks. In particular, the optimized trade-off model of a growing network is described, as well as models showing the explosive percolation phenomenon.Less
This chapter demonstrates how a universal requirement for optimality leads to the complex structural organization of a network. It discusses a long-lasting criticism of the preferential concept and describes existing approaches to the optimization-driven evolution of complex networks. In particular, the optimized trade-off model of a growing network is described, as well as models showing the explosive percolation phenomenon.
Paolo Agnolucci
- Published in print:
- 2011
- Published Online:
- May 2011
- ISBN:
- 9780199584505
- eISBN:
- 9780191725012
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199584505.003.0007
- Subject:
- Economics and Finance, Macro- and Monetary Economics
The objective of ETRs is to improve the environment (for example, by reducing carbon emissions) while reducing other taxes which may have a negative economic effect. Often ETRs also have the ...
More
The objective of ETRs is to improve the environment (for example, by reducing carbon emissions) while reducing other taxes which may have a negative economic effect. Often ETRs also have the objective of increasing employment. The aim of this chapter is to estimate the effect on the demand for energy and the level of unemployment of the UK and German ETRs that have been implemented. In order to do this, we estimate a specification based on a translog cost function which allows us to model the cross-price elasticities among capital, labour, energy, material, and services.Less
The objective of ETRs is to improve the environment (for example, by reducing carbon emissions) while reducing other taxes which may have a negative economic effect. Often ETRs also have the objective of increasing employment. The aim of this chapter is to estimate the effect on the demand for energy and the level of unemployment of the UK and German ETRs that have been implemented. In order to do this, we estimate a specification based on a translog cost function which allows us to model the cross-price elasticities among capital, labour, energy, material, and services.
Robert G. Chambers
- Published in print:
- 2021
- Published Online:
- December 2020
- ISBN:
- 9780190063016
- eISBN:
- 9780190063047
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780190063016.003.0004
- Subject:
- Economics and Finance, Econometrics, Microeconomics
Three generic economic optimization problems (expenditure (cost) minimization, revenue maximization, and profit maximization) are studied using the mathematical tools developed in Chapters 2 and 3. ...
More
Three generic economic optimization problems (expenditure (cost) minimization, revenue maximization, and profit maximization) are studied using the mathematical tools developed in Chapters 2 and 3. Conjugate duality results are developed for each. The resulting dual representations (E(q;y), R(p,x), and π(p,q)) are shown to characterize all of the economically relevant information in, respectively, V(y), Y(x), and Gr(≽(y)). The implications of different restrictions on ≽(y) for the dual representations are examined.Less
Three generic economic optimization problems (expenditure (cost) minimization, revenue maximization, and profit maximization) are studied using the mathematical tools developed in Chapters 2 and 3. Conjugate duality results are developed for each. The resulting dual representations (E(q;y), R(p,x), and π(p,q)) are shown to characterize all of the economically relevant information in, respectively, V(y), Y(x), and Gr(≽(y)). The implications of different restrictions on ≽(y) for the dual representations are examined.
Tad Hogg
- Published in print:
- 2005
- Published Online:
- November 2020
- ISBN:
- 9780195177374
- eISBN:
- 9780197562260
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780195177374.003.0019
- Subject:
- Computer Science, Mathematical Theory of Computation
Phase transitions have long been studied empirically in various combinatorial searches and theoretically in simplified models [91, 264, 301, 490]. The ...
More
Phase transitions have long been studied empirically in various combinatorial searches and theoretically in simplified models [91, 264, 301, 490]. The analogy with statistical physics [397], explored throughout this volume, shows how the many local choices made during search relate to global properties such as the resulting search cost. These studies have led to a better understanding of typical search behaviors [514] and improved search methods [195, 247, 261, 432, 433]. Among the current research questions in this field are the range of algorithms exhibiting the transition behavior and the algorithm-independent problem properties associated with the difficult instances concentrated near the transition. Towards this end, the present chapter examines quantum computer [123, 126, 158, 486] algorithms for nondeterministic polynomial (NP) combinatorial search problems [191]. As with many conventional methods, they exhibit the easy-hard-easy pattern of computational cost as the degree of constraint in the problems varies. We describe how properties of the search space affect the algorithms and identify an additional structural property, the energy gap, motivated by one quantum algorithm but applicable to a variety of techniques, both quantum and classical. Thus, the study of quantum search algorithms not only extends the range of algorithms exhibiting phase transitions, but also helps identify underlying structural properties. Specifically, the next two sections describe a class of hard search problems and the form of quantum search algorithms proposed to date. The remainder of the chapter presents algorithm behaviors, relevant problem structure, arid an approximate asymptotic analysis of their cost scaling. The final section discusses various open issues in designing and evaluating quantum algorithms, and relating their behavior to problem structure. The k-satisfiability (k -SAT) problem, as discussed earlier in this volume, consists of n Boolean variables and m clauses. A clause is a logical OR of k variables, each of which may be negated. A solution is an assignment, that is, a value for each variable, TRUE or FALSE, satisfying all the clauses. An assignment is said to conflict with any clause it does not satisfy.
Less
Phase transitions have long been studied empirically in various combinatorial searches and theoretically in simplified models [91, 264, 301, 490]. The analogy with statistical physics [397], explored throughout this volume, shows how the many local choices made during search relate to global properties such as the resulting search cost. These studies have led to a better understanding of typical search behaviors [514] and improved search methods [195, 247, 261, 432, 433]. Among the current research questions in this field are the range of algorithms exhibiting the transition behavior and the algorithm-independent problem properties associated with the difficult instances concentrated near the transition. Towards this end, the present chapter examines quantum computer [123, 126, 158, 486] algorithms for nondeterministic polynomial (NP) combinatorial search problems [191]. As with many conventional methods, they exhibit the easy-hard-easy pattern of computational cost as the degree of constraint in the problems varies. We describe how properties of the search space affect the algorithms and identify an additional structural property, the energy gap, motivated by one quantum algorithm but applicable to a variety of techniques, both quantum and classical. Thus, the study of quantum search algorithms not only extends the range of algorithms exhibiting phase transitions, but also helps identify underlying structural properties. Specifically, the next two sections describe a class of hard search problems and the form of quantum search algorithms proposed to date. The remainder of the chapter presents algorithm behaviors, relevant problem structure, arid an approximate asymptotic analysis of their cost scaling. The final section discusses various open issues in designing and evaluating quantum algorithms, and relating their behavior to problem structure. The k-satisfiability (k -SAT) problem, as discussed earlier in this volume, consists of n Boolean variables and m clauses. A clause is a logical OR of k variables, each of which may be negated. A solution is an assignment, that is, a value for each variable, TRUE or FALSE, satisfying all the clauses. An assignment is said to conflict with any clause it does not satisfy.
Kelly Chance and Randall V. Martin
- Published in print:
- 2017
- Published Online:
- May 2017
- ISBN:
- 9780199662104
- eISBN:
- 9780191748370
- Item type:
- chapter
- Publisher:
- Oxford University Press
- DOI:
- 10.1093/oso/9780199662104.003.0011
- Subject:
- Physics, Geophysics, Atmospheric and Environmental Physics
This chapter explores several of the most common and useful approaches to atmospheric data fitting as well as the process of using air mass factors to produce vertical atmospheric column abundances ...
More
This chapter explores several of the most common and useful approaches to atmospheric data fitting as well as the process of using air mass factors to produce vertical atmospheric column abundances from line-of-sight slant columns determined by data fitting. An atmospheric spectrum or other type of atmospheric sounding is usually fitted to a parameterized physical model by minimizing a cost function, usually chi-squared. Linear fitting, when the model of the measurements is linear in the model parameters is described, followed by the more common nonlinear fitting case. For nonlinear fitting, the standard Levenberg-Marquardt method is described, followed by the use of optimal estimation, one of several retrieval methods that make use of a priori information to providing regularization for the solution. In the context of optimal estimation, weighting functions, contribution functions, and averaging kernels are described. The Twomey-Tikhonov regularization procedure is presented. Correlated parameters, with the important example of Earth’s atmospheric ozone, are discussed.Less
This chapter explores several of the most common and useful approaches to atmospheric data fitting as well as the process of using air mass factors to produce vertical atmospheric column abundances from line-of-sight slant columns determined by data fitting. An atmospheric spectrum or other type of atmospheric sounding is usually fitted to a parameterized physical model by minimizing a cost function, usually chi-squared. Linear fitting, when the model of the measurements is linear in the model parameters is described, followed by the more common nonlinear fitting case. For nonlinear fitting, the standard Levenberg-Marquardt method is described, followed by the use of optimal estimation, one of several retrieval methods that make use of a priori information to providing regularization for the solution. In the context of optimal estimation, weighting functions, contribution functions, and averaging kernels are described. The Twomey-Tikhonov regularization procedure is presented. Correlated parameters, with the important example of Earth’s atmospheric ozone, are discussed.