NDLI: A new algorithm for the recursive identification of stochastic systems using an automaton with slowly growing memory

Content Provider	IEEE Xplore Digital Library
Author	Kurtz, B.D. Caines, P.E.
Copyright Year	1976
Description	Author affiliation: Harvard University, Cambridge, Massachusetts (Caines, P.E.) \|\| Howden Applied Research, Toronto, Canada (Kurtz, B.D.)
Abstract	Consider a siscrete time system or process with i.i.d. outputs, X1,X2,... The distribution of Xi's is characterized by some unknown parameter, ¿ which is an element of ¿, a subset of Z+, the positive integers. We propose to identify the parameter ¿ with an automaton which is realized by the following algorithm: The Xi's are observed sequentially. At instant i, a current best estimate (CBE) of ¿¿¿ is generated, based on Xi alone. The best estimate to date (BED) of ¿, at any instant, will be the particular element of ¿ which was previously the CBE of ¿ for the greatest number of consecutive instants. In the implementation of the algorithm, the state of te automaton will consist of the following four elements: the best estimate to date; the maximum number of consecutive times that this BED was the CBE of ¿; the current best estimate of ¿ based on the latest value of Xi (= candidate for BED); and the number of consecutive times to date that this value has been the CBE of ¿. It is shown that the BED converges strongly to the correct parameter. The following three specific applications are discussed: 1) Identification of the most probable value of a single sample from a set of discrete i.i.d. random variables. 2) Identification of the parameter of an observed sequence of i.i.d. Bernoulli random variables. 3) Identification of the parameters of a moving average process. (Notice that the observations of the system output in this case are not i.i.d.). The rate of convergence of the algorithm is shown to exceed that of other proposed recursive algorithms [1] for parameter identification. Furthermore, the amount of memory required is shown to grow as log log i, a rate significantly slower than that required by other algorithms. It is also shown that for a very large class of systems, convergence of parameter estimates is impossible without acess to an unbounded memory.
Starting Page	947
Ending Page	950
File Size	331371
Page Count	4
File Format	PDF
DOI	10.1109/CDC.1976.267863
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1976-12-01
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Stochastic systems Automata Tellurium Testing Physics computing Random variables
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