NDLI: An Approximation to the Stationary Distribution of a Nearly Completely Decomposable Markov Chain and Its Error Bound

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Haviv, Moshe Ritov, Y.
Copyright Year	1986
Abstract	In Haviv (Ph.D. dissertation, Yale Univ., New Haven, CT, 1983) an approximation procedure for computing the stationary distribution of a nearly completely decomposable (NCD) Markov chain is suggested. There and in Haviv (this Journal, 7 (1986), pp. 589593) the incurred error is analyzed. In particular, a series expansion for the error is developed. Courtois and Semal (J. Assoc. Comput. Mach., 31 (1984), pp. 804825) independently of us, replaced this point approximation with a set of points. Using algebraic methods, they proved that the exact distribution lies in the convex set spanned by this set. We give a probabilistic interpretation for this set and then obtain their results in a more elementary way. We compute the convex combination leading to the exact distribution and develop a bound on it. Finally, we show how approximation to this convex combination leads to an error reduction in a cui`rent approximation. It is the first time that a probabilistic approach is made in order to analyze NCD Markov chains.
Starting Page	583
Ending Page	588
Page Count	6
File Format	PDF
ISSN	01965212
DOI	10.1137/0607064
Journal	SIAM Journal on Algebraic Discrete Methods (SJAMDU)
Issue Number	4
Volume Number	7
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-07-17
Access Restriction	Subscribed
Subject Keyword	Markov chains
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in