IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/2012058.html

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. Fleurbaey,Marc & Maniquet,François, 2011. "A Theory of Fairness and Social Welfare," Cambridge Books, Cambridge University Press, number 9780521715348, January.
    2. 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.
    3. 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.
    4. 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.
    5. 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).
    6. 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.
    7. 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).
    8. 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.
    9. Dehez, Pierre & Ferey, Samuel, 2013. "How to share joint liability: A cooperative game approach," Mathematical Social Sciences, Elsevier, vol. 66(1), pages 44-50.
    10. Gaertner,Wulf & Schokkaert,Erik, 2011. "Empirical Social Choice," Cambridge Books, Cambridge University Press, number 9781107013940, January.
    11. 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).
    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. 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).
    6. Pascal Mossay & Takatoshi Tabuchi, 2015. "Preferential Trade Agreements Harm Third Countries," Economic Journal, Royal Economic Society, vol. 125(589), pages 1964-1985, December.
    7. 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.
    8. 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.
    9. 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.
    10. 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).
    11. HOSSEINZADEH LOTFI, Farhad & HATAMI-MARBINI, Adel & AGRELL, Per & GHOLAMI, Kobra, 2013. "Centralized resource reduction and target setting under DEA control," LIDAM Discussion Papers CORE 2013005, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    12. NESTEROV, Yurii, 2013. "Universal gradient methods for convex optimization problems," LIDAM Discussion Papers CORE 2013026, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    13. CALO-BLANCO, Aitor, 2012. "The compensation problem with fresh starts," LIDAM Discussion Papers CORE 2012036, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    14. Ana Mauleon & Vincent Vannetelbosch, 2013. "Relative Concerns and Delays in Bargaining with Private Information," Games, MDPI, vol. 4(3), pages 1-10, June.
    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. Jean-François Mertens & Anna Rubinchik, 2013. "Equilibria in an overlapping generations model with transfer policies and exogenous growth," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 54(3), pages 537-595, November.
    17. 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.
    18. Kirchsteiger, Georg & Mantovani, Marco & Mauleon, Ana & Vannetelbosch, Vincent, 2016. "Limited farsightedness in network formation," Journal of Economic Behavior & Organization, Elsevier, vol. 128(C), pages 97-120.
    19. Nora, Vladyslav & Uno, Hiroshi, 2014. "Saddle functions and robust sets of equilibria," Journal of Economic Theory, Elsevier, vol. 150(C), pages 866-877.
    20. 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.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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.