IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/2012058.html
   My bibliography  Save this paper

Finding the stationary states of Markov chains by iterative methods

Author

Listed:
  • NESTEROV, Yurii

    (Université catholique de Louvain, CORE, Belgium)

  • NEMIROVSKI, Arkadi

    (Georgia Institute of Technology, Atlanta, USA)

Abstract

In this paper, we develop new methods for approximating dominant eigenvector of column-stochastic matrices. We analyze the Google matrix, and present an averaging scheme with linear rate of convergence in terms of 1-norm distance. For extending this convergence result onto general case, we assume existence of a positive row in the matrix. Our new numerical scheme, the Reduced Power Method (RPM), can be seen as a proper averaging of the power iterates of a reduced stochastic matrix. We analyze also the usual Power Method (PM) and obtain convenient conditions for its linear rate of convergence with respect to 1-norm.

Suggested Citation

  • NESTEROV, Yurii & NEMIROVSKI, Arkadi, 2012. "Finding the stationary states of Markov chains by iterative methods," LIDAM Discussion Papers CORE 2012058, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:2012058
    as

    Download full text from publisher

    File URL: https://sites.uclouvain.be/core/publications/coredp/coredp2012.html
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Duranton, Gilles & Martin, Philippe & Mayer, Thierry & Mayneris, Florian, 2010. "The Economics of Clusters: Lessons from the French Experience," OUP Catalogue, Oxford University Press, number 9780199592203, Decembrie.
    2. Jean‐Francois Carpantier & Besik Samkharadze, 2013. "The Asymmetric Commodity Inventory Effect on the Optimal Hedge Ratio," Journal of Futures Markets, John Wiley & Sons, Ltd., vol. 33(9), pages 868-888, September.
    3. DUFAYS, Arnaud, 2012. "Infinite-state Markov-switching for dynamic volatility and correlation models," LIDAM Discussion Papers CORE 2012043, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. BEDAYO, Mikel & MAULEON, Ana & VANNETELBOSCH, Vincent, 2012. "Bargaining and delay in trading networks," LIDAM Discussion Papers CORE 2012046, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Miguel Jara & Dimitri Paolini & Juan Dios Tena Horrillo, 2015. "Management Efficiency in Football: An Empirical Analysis of Two Extreme Cases," Managerial and Decision Economics, John Wiley & Sons, Ltd., vol. 36(5), pages 286-298, July.
    6. Dehez, Pierre & Ferey, Samuel, 2013. "How to share joint liability: A cooperative game approach," Mathematical Social Sciences, Elsevier, vol. 66(1), pages 44-50.
    7. Mendolicchio Concetta & Paolini Dimitri & Pietra Tito, 2012. "Asymmetric Information And Overeducation," The B.E. Journal of Economic Analysis & Policy, De Gruyter, vol. 12(1), pages 1-29, October.
    8. Fleurbaey,Marc & Maniquet,François, 2011. "A Theory of Fairness and Social Welfare," Cambridge Books, Cambridge University Press, number 9780521887427, November.
    9. Berardino Cesi & Dimitri Paolini, 2014. "Peer Group and Distance: When Widening University Participation is Better," Manchester School, University of Manchester, vol. 82, pages 110-132, December.
    10. Gaertner,Wulf & Schokkaert,Erik, 2011. "Empirical Social Choice," Cambridge Books, Cambridge University Press, number 9781107013940, November.
    11. ROELS, Guillaume & CHEVALIER, Philippe & WEI, Ying, 2012. "United we stand? Coordinating capacity investment and allocation in joint ventures," LIDAM Discussion Papers CORE 2012045, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Wang, Cindy Shin-Huei & Bauwens, Luc & Hsiao, Cheng, 2013. "Forecasting a long memory process subject to structural breaks," Journal of Econometrics, Elsevier, vol. 177(2), pages 171-184.
    2. ROELS, Guillaume & CHEVALIER, Philippe & WEI, Ying, 2012. "United we stand? Coordinating capacity investment and allocation in joint ventures," LIDAM Discussion Papers CORE 2012045, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. WUNSCH, Guillaume & MOUCHART, Michel & RUSSO, Federica, 2012. "Functions and mechanisms in structural-modelling explanations," LIDAM Discussion Papers CORE 2012056, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. Sudipto Bhattacharya & Claude d’Aspremont & Sergei Guriev & Debapriya Sen & Yair Tauman, 2014. "Cooperation in R&D: Patenting, Licensing, and Contracting," International Series in Operations Research & Management Science, in: Kalyan Chatterjee & William Samuelson (ed.), Game Theory and Business Applications, edition 2, chapter 0, pages 265-286, Springer.
    5. Pascal Mossay & Takatoshi Tabuchi, 2015. "Preferential Trade Agreements Harm Third Countries," Economic Journal, Royal Economic Society, vol. 125(589), pages 1964-1985, December.
    6. Mertens, Jean-François & Rubinchik, Anna, 2015. "Pareto Optimality Of The Golden Rule Equilibrium In An Overlapping Generations Model With Production And Transfers," Macroeconomic Dynamics, Cambridge University Press, vol. 19(8), pages 1780-1799, December.
    7. DUFAYS, Arnaud, 2012. "Infinite-state Markov-switching for dynamic volatility and correlation models," LIDAM Discussion Papers CORE 2012043, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. Dirk Van de gaer & Joost Vandenbossche & José Luis Figueroa, 2014. "Children's Health Opportunities and Project Evaluation: Mexico's Oportunidades Program," The World Bank Economic Review, World Bank, vol. 28(2), pages 282-310.
    9. Mendolicchio Concetta & Paolini Dimitri & Pietra Tito, 2012. "Asymmetric Information And Overeducation," The B.E. Journal of Economic Analysis & Policy, De Gruyter, vol. 12(1), pages 1-29, October.
    10. Claude, DASPREMONT & Rodolphe, DOS SANTOS FERREIRA & Jacques, THEPOT, 2007. "Hawks and doves in segmented markets : a formal approach to competitive aggressiveness," Discussion Papers (ECON - Département des Sciences Economiques) 2007039, Université catholique de Louvain, Département des Sciences Economiques.
    11. Dehez, Pierre & Ferey, Samuel, 2013. "How to share joint liability: A cooperative game approach," Mathematical Social Sciences, Elsevier, vol. 66(1), pages 44-50.
    12. Bocart, Fabian Y.R.P. & Hafner, Christian M., 2015. "Fair Revaluation of Wine as an Investment," Journal of Wine Economics, Cambridge University Press, vol. 10(2), pages 190-203, November.
    13. Caulier, Jean-François & Mauleon, Ana & Vannetelbosch, Vincent, 2015. "Allocation rules for coalitional network games," Mathematical Social Sciences, Elsevier, vol. 78(C), pages 80-88.
    14. DEVOLDER, Olivier & GLINEUR, François & NESTEROV, Yurii, 2013. "First-order methods with inexact oracle: the strongly convex case," LIDAM Discussion Papers CORE 2013016, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    15. Christophe Bravard & Sudipta Sarangi & ANA MAULEON & JOSE J. SEMPERE-MONERRIS & VINCENT VANNETELBOSCH, 2016. "Contractually Stable Alliances," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 18(2), pages 212-225, April.
    16. Thierry Bréchet & Carmen Camacho & Vladimir M. Veliov, 2012. "Adaptive Model-Predictive Climate Policies in a Multi-Country Setting," Documents de travail du Centre d'Economie de la Sorbonne 12029, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    17. Jacques Dreze, 2016. "Existence and multiplicity of temporary equilibria under nominal price rigidities," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 62(1), pages 279-298, June.
    18. Dehez Pierre & Poukens Sophie, 2014. "The Shapley Value as a Guide to FRAND Licensing Agreements," Review of Law & Economics, De Gruyter, vol. 10(3), pages 265-284, November.
    19. Thomas Baudin & David de la Croix & Paula E. Gobbi, 2015. "Fertility and Childlessness in the United States," American Economic Review, American Economic Association, vol. 105(6), pages 1852-1882, June.
    20. Thierry Bréchet & Yann Ménière & Pierre M. Picard, 2016. "The Clean Development Mechanism in a world carbon market," Canadian Journal of Economics, Canadian Economics Association, vol. 49(4), pages 1569-1598, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:cor:louvco:2012058. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Alain GILLIS (email available below). General contact details of provider: https://edirc.repec.org/data/coreebe.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.