Editing Particle filter

{{Short description|Type of Monte Carlo algorithms for signal processing and statistical inference}}
{{About|mathematical algorithms|devices to filter particles from air|Air filter}}
{{Use American English|date=January 2019}}

'''Particle filters''', also known as '''sequential Monte Carlo''' methods, are a set of [[Monte Carlo method|Monte Carlo]] algorithms used to find approximate solutions for [[Filtering problem (stochastic processes)|filtering problems]] for nonlinear state-space systems, such as [[signal processing]] and [[Bayesian inference|Bayesian statistical inference]].<ref name="Wills">{{cite journal |last1=Wills |first1=Adrian G. |last2=Schön |first2=Thomas B. |title=Sequential Monte Carlo: A Unified Review |journal=Annual Review of Control, Robotics, and Autonomous Systems |date=3 May 2023 |volume=6 |issue=1 |pages=159–182 |doi=10.1146/annurev-control-042920-015119 |s2cid=255638127 |language=en |issn=2573-5144|doi-access=free }}</ref> The [[Filtering problem (stochastic processes)|filtering problem]] consists of estimating the internal states in [[dynamical systems]] when partial observations are made and random perturbations are present in the sensors as well as in the dynamical system. The objective is to compute the [[posterior probability|posterior distributions]] of the states of a [[Markov process]], given the noisy and partial observations. The term "particle filters" was first coined in 1996 by Pierre Del Moral about [[mean-field particle methods|mean-field interacting particle methods]] used in [[fluid mechanics]] since the beginning of the 1960s.<ref name="dm962">{{cite journal|last1 = Del Moral|first1 = Pierre|title = Non Linear Filtering: Interacting Particle Solution.|journal = Markov Processes and Related Fields|date = 1996|volume = 2|issue = 4|pages = 555–580|url = http://people.bordeaux.inria.fr/pierre.delmoral/delmoral96nonlinear.pdf}}</ref> The term "Sequential Monte Carlo" was coined by [[Jun S. Liu]] and Rong Chen in 1998.<ref>{{Cite journal|last1=Liu|first1=Jun S.|last2=Chen|first2=Rong|date=1998-09-01|title=Sequential Monte Carlo Methods for Dynamic Systems|journal=Journal of the American Statistical Association|volume=93|issue=443|pages=1032–1044|doi=10.1080/01621459.1998.10473765|issn=0162-1459}}</ref>

Particle filtering uses a set of particles (also called samples) to represent the [[posterior distribution]] of a [[stochastic process]] given the noisy and/or partial observations. The state-space model can be nonlinear and the initial state and noise distributions can take any form required. Particle filter techniques provide a well-established methodology<ref name="dm962" /><ref name=":22">{{cite journal|last1 = Del Moral|first1 = Pierre|title = Measure Valued Processes and Interacting Particle Systems. Application to Non Linear Filtering Problems|journal = Annals of Applied Probability|date = 1998|edition = Publications du Laboratoire de Statistique et Probabilités, 96-15 (1996)|volume = 8|issue = 2|pages = 438–495|url = http://projecteuclid.org/download/pdf_1/euclid.aoap/1028903535|doi = 10.1214/aoap/1028903535|doi-access = free}}</ref><ref name=":1">{{Cite book|title = Feynman-Kac formulae. Genealogical and interacting particle approximations.|last = Del Moral|first = Pierre|publisher = Springer. Series: Probability and Applications|year = 2004|isbn = 978-0-387-20268-6|url = https://www.springer.com/gp/book/9780387202686|pages = 556}}</ref> for generating samples from the required distribution without requiring assumptions about the state-space model or the state distributions. However, these methods do not perform well when applied to very high-dimensional systems.

Particle filters update their prediction in an approximate (statistical) manner. The samples from the distribution are represented by a set of particles; each particle has a likelihood weight assigned to it that represents the [[probability]] of that particle being sampled from the [[probability density function]]. Weight disparity leading to weight collapse is a common issue encountered in these filtering algorithms. However, it can be mitigated by including a resampling step before the weights become uneven. Several adaptive resampling criteria can be used including the [[variance]] of the weights and the relative [[entropy]] concerning the uniform distribution.<ref name=":0">{{cite journal|last1 = Del Moral|first1 = Pierre|last2 = Doucet|first2 = Arnaud|last3 = Jasra|first3 = Ajay|title = On Adaptive Resampling Procedures for Sequential Monte Carlo Methods|journal = Bernoulli|date = 2012|volume = 18|issue = 1|pages = 252–278|url = http://hal.inria.fr/docs/00/33/25/83/PDF/RR-6700.pdf|doi = 10.3150/10-bej335|s2cid = 4506682|doi-access = free}}</ref> In the resampling step, the particles with negligible weights are replaced by new particles in the proximity of the particles with higher weights.

From the statistical and probabilistic point of view, particle filters may be interpreted as [[mean-field particle methods|mean-field particle]] interpretations of [[Feynman–Kac formula|Feynman-Kac]] probability measures.<ref name="dp042">{{cite book|last = Del Moral|first = Pierre|title = Feynman-Kac formulae. Genealogical and interacting particle approximations|year = 2004|publisher = Springer|quote = Series: Probability and Applications|url = https://www.springer.com/mathematics/probability/book/978-0-387-20268-6|pages = 575|isbn = 9780387202686|series = Probability and its Applications}}</ref><ref name="dmm002">{{cite book|last1 = Del Moral|first1 = Pierre|last2 = Miclo|first2 = Laurent|contribution = Branching and Interacting Particle Systems Approximations of Feynman-Kac Formulae with Applications to Non-Linear Filtering|title=Séminaire de Probabilités XXXIV|editor1=Jacques Azéma |editor2=Michel Ledoux |editor3=Michel Émery |editor4=Marc Yor|series = Lecture Notes in Mathematics|date = 2000|volume = 1729|pages = 1–145|url = http://archive.numdam.org/ARCHIVE/SPS/SPS_2000__34_/SPS_2000__34__1_0/SPS_2000__34__1_0.pdf|doi = 10.1007/bfb0103798|isbn = 978-3-540-67314-9}}</ref><ref name="dmm00m2">{{cite journal|last1 = Del Moral|first1 = Pierre|last2 = Miclo|first2 = Laurent|title = A Moran particle system approximation of Feynman-Kac formulae.|journal = Stochastic Processes and Their Applications|date = 2000|volume = 86|issue = 2|pages = 193–216|doi = 10.1016/S0304-4149(99)00094-0| s2cid=122757112 |doi-access = }}</ref><ref name="dp13" /><ref>{{Cite journal|title = Particle methods: An introduction with applications | journal= ESAIM: Proc.| doi = 10.1051/proc/201444001 | volume=44| pages=1–46| year= 2014| last1= Moral| first1= Piere Del| last2= Doucet| first2= Arnaud| doi-access= free}}</ref> These particle integration techniques were developed in [[molecular chemistry]] and [[computational physics]] by [[Ted Harris (mathematician)|Theodore E. Harris]] and [[Herman Kahn]] in 1951, [[Marshall Rosenbluth|Marshall N. Rosenbluth]] and [[Arianna W. Rosenbluth]] in 1955,<ref name=":5">{{cite journal|last1 = Rosenbluth|first1 = Marshall, N.|last2 = Rosenbluth|first2 = Arianna, W.|title = Monte-Carlo calculations of the average extension of macromolecular chains|journal = J. Chem. Phys.|date = 1955|volume = 23|issue = 2|pages = 356–359|doi=10.1063/1.1741967|bibcode = 1955JChPh..23..356R|s2cid = 89611599|doi-access = free}}</ref> and more recently by Jack H. Hetherington in 1984.<ref name="h84" /> In computational physics, these Feynman-Kac type path particle integration methods are also used in [[Quantum Monte Carlo]], and more specifically [[Diffusion Monte Carlo|Diffusion Monte Carlo methods]].<ref name="dm-esaim032">{{cite journal|last1 = Del Moral|first1 = Pierre|title = Particle approximations of Lyapunov exponents connected to Schrödinger operators and Feynman-Kac semigroups|journal = ESAIM Probability & Statistics|date = 2003|volume = 7|pages = 171–208|url = http://journals.cambridge.org/download.php?file=%2FPSS%2FPSS7%2FS1292810003000016a.pdf&code=a0dbaa7ffca871126dc05fe2f918880a|doi = 10.1051/ps:2003001|doi-access = free}}</ref><ref name="caffarel12">{{cite journal|last1 = Assaraf|first1 = Roland|last2 = Caffarel|first2 = Michel|last3 = Khelif|first3 = Anatole|title = Diffusion Monte Carlo Methods with a fixed number of walkers|journal = Phys. Rev. E|url = http://qmcchem.ups-tlse.fr/files/caffarel/31.pdf|date = 2000|volume = 61|issue = 4|pages = 4566–4575|doi = 10.1103/physreve.61.4566|pmid = 11088257|bibcode = 2000PhRvE..61.4566A|url-status = dead|archive-url = https://web.archive.org/web/20141107015724/http://qmcchem.ups-tlse.fr/files/caffarel/31.pdf|archive-date = 2014-11-07}}</ref><ref name="caffarel22">{{cite journal|last1 = Caffarel|first1 = Michel|last2 = Ceperley|first2 = David|last3 = Kalos|first3 = Malvin|title = Comment on Feynman-Kac Path-Integral Calculation of the Ground-State Energies of Atoms|journal = Phys. Rev. Lett.|date = 1993|volume = 71|issue = 13|doi = 10.1103/physrevlett.71.2159|bibcode = 1993PhRvL..71.2159C|pages=2159|pmid=10054598}}</ref> Feynman-Kac interacting particle methods are also strongly related to [[Genetic algorithm|mutation-selection genetic algorithms]] currently used in [[evolutionary computation]] to solve complex optimization problems.

The particle filter methodology is used to solve [[Hidden Markov model|Hidden Markov Model]] (HMM) and [[nonlinear filter]]ing problems. With the notable exception of linear-Gaussian signal-observation models ([[Kalman filter]]) or wider classes of models (Benes filter<ref>{{Cite journal|title = Asymptotic stability of beneš filters|journal = Stochastic Analysis and Applications|date = January 1, 1999|issn = 0736-2994|pages = 1053–1074|volume = 17|issue = 6|doi = 10.1080/07362999908809648|first = D. L.|last = Ocone}}</ref>), Mireille Chaleyat-Maurel and Dominique Michel proved in 1984 that the sequence of posterior distributions of the random states of a signal, given the observations (a.k.a. optimal filter), has no finite recursion.<ref>{{Cite journal|title = Des resultats de non existence de filtre de dimension finie|journal = Stochastics|date = January 1, 1984|issn = 0090-9491|pages = 83–102|volume = 13|issue = 1–2|doi = 10.1080/17442508408833312|first1 = Mireille Chaleyat|last1 = Maurel|first2 = Dominique|last2 = Michel}}</ref> Various other numerical methods based on fixed grid approximations, [[Markov chain Monte Carlo|Markov Chain Monte Carlo]] techniques, conventional linearization, [[extended Kalman filter]]s, or determining the best linear system (in the expected cost-error sense) are unable to cope with large-scale systems, unstable processes, or insufficiently smooth nonlinearities.

Particle filters and Feynman-Kac particle methodologies find application in [[signal processing|signal and image processing]], [[Bayesian inference]], [[machine learning]], [[Rare Event Sampling|risk analysis and rare event sampling]], [[engineering]] [[robotics|and robotics]], [[artificial intelligence]], [[bioinformatics]],<ref name=":PFOBC">{{cite journal |doi=10.1186/s12864-019-5720-3 |pmid=31189480 |pmc=6561847 |arxiv=1902.03188 |title=Scalable optimal Bayesian classification of single-cell trajectories under regulatory model uncertainty |journal=BMC Genomics |volume=20 |issue=Suppl 6 |pages=435 |year=2019 |last1=Hajiramezanali |first1=Ehsan |last2=Imani |first2=Mahdi |last3=Braga-Neto |first3=Ulisses |last4=Qian |first4=Xiaoning |last5=Dougherty |first5=Edward R. |bibcode=2019arXiv190203188H |doi-access=free }}</ref> [[phylogenetics]], [[computational science]], [[economics]] [[financial mathematics|and]] [[mathematical finance]], [[molecular chemistry]], [[computational physics]], [[pharmacokinetics]], quantitative risk and insurance<ref>{{Cite book |last1=Cruz |first1=Marcelo G. |url=https://onlinelibrary.wiley.com/doi/book/10.1002/9781118573013 |title=Fundamental Aspects of Operational Risk and Insurance Analytics: A Handbook of Operational Risk |last2=Peters |first2=Gareth W. |last3=Shevchenko |first3=Pavel V. |date=2015-02-27 |publisher=Wiley |isbn=978-1-118-11839-9 |edition=1 |language=en |doi=10.1002/9781118573013}}</ref><ref>{{Cite book |last1=Peters |first1=Gareth W. |url=https://onlinelibrary.wiley.com/doi/book/10.1002/9781118909560 |title=Advances in Heavy Tailed Risk Modeling: A Handbook of Operational Risk |last2=Shevchenko |first2=Pavel V. |date=2015-02-20 |publisher=Wiley |isbn=978-1-118-90953-9 |edition=1 |language=en |doi=10.1002/9781118909560}}</ref> and other fields.

== History ==

=== Heuristic-like algorithms ===
From a statistical and probabilistic viewpoint, particle filters belong to the class of [[branching process|branching]]/[[genetic algorithms|genetic type algorithms]], and [[mean-field particle methods|mean-field type interacting particle methodologies.]] The interpretation of these particle methods depends on the scientific discipline. In [[Evolutionary computation|Evolutionary Computing]], [[mean-field particle methods|mean-field genetic type particle]] methodologies are often used as heuristic and natural search algorithms (a.k.a. [[Metaheuristic]]). In [[computational physics]] and [[molecular chemistry]], they are used to solve Feynman-Kac [[path integration]] problems or to compute Boltzmann-Gibbs measures, top eigenvalues, and [[Ground state|ground states]] of [[Schrödinger equation|Schrödinger]] operators. In [[Biology]] and [[Genetics]], they represent the evolution of a population of individuals or genes in some environment.

The origins of mean-field type [[Evolutionary algorithm|evolutionary computational techniques]] can be traced back to 1950 and 1954 with [[Alan Turing|Alan Turing's]] work on genetic type mutation-selection learning machines<ref>{{cite journal|last1 = Turing|first1 = Alan M.|title = Computing machinery and intelligence|journal = Mind|volume = LIX|issue = 238|pages = 433–460|doi = 10.1093/mind/LIX.236.433 |date = October 1950}}</ref> and the articles by [[Nils Aall Barricelli]] at the [[Institute for Advanced Study]] in [[Princeton, New Jersey]].<ref>{{cite journal|last = Barricelli|first = Nils Aall|year = 1954|author-link = Nils Aall Barricelli|title = Esempi numerici di processi di evoluzione|journal = Methodos|pages = 45–68}}</ref><ref>{{cite journal|last = Barricelli|first = Nils Aall|year = 1957|author-link = Nils Aall Barricelli|title = Symbiogenetic evolution processes realized by artificial methods|journal = Methodos|pages = 143–182}}</ref> The first trace of particle filters in [[Statistics|statistical methodology]] dates back to the mid-1950s; the 'Poor Man's Monte Carlo',<ref>{{Cite journal|title = Poor Man's Monte Carlo |journal = Journal of the Royal Statistical Society. Series B (Methodological) |jstor = 2984008 | volume=16 |issue = 1 | pages=23–38|last1 = Hammersley |first1 = J. M. |last2 = Morton |first2 = K. W. |year = 1954 |doi = 10.1111/j.2517-6161.1954.tb00145.x }}</ref> that was proposed by [[John Hammersley]] et al., in 1954, contained hints of the genetic type particle filtering methods used today. In 1963, [[Nils Aall Barricelli]] simulated a genetic type algorithm to mimic the ability of individuals to play a simple game.<ref>{{cite journal|last = Barricelli|first = Nils Aall|year = 1963|title = Numerical testing of evolution theories. Part II. Preliminary tests of performance, symbiogenesis and terrestrial life|journal = Acta Biotheoretica|volume = 16|issue = 3–4|pages = 99–126|doi = 10.1007/BF01556602|s2cid = 86717105}}</ref> In [[Evolutionary computation|evolutionary computing]] literature, genetic-type mutation-selection algorithms became popular through the seminal work of [[John Henry Holland|John Holland]] in the early 1970s, particularly his book<ref>{{Cite web|title = Adaptation in Natural and Artificial Systems {{!}} The MIT Press|url = https://mitpress.mit.edu/index.php?q=books/adaptation-natural-and-artificial-systems|website = mitpress.mit.edu|access-date = 2015-06-06}}</ref> published in 1975.

In Biology and [[Genetics]], the Australian geneticist [[Alex Fraser (scientist)|Alex Fraser]] also published in 1957 a series of papers on the genetic type simulation of [[artificial selection]] of organisms.<ref>{{cite journal|last = Fraser|first = Alex|author-link = Alex Fraser (scientist)|year = 1957|title = Simulation of genetic systems by automatic digital computers. I. Introduction|journal = Aust. J. Biol. Sci.|volume = 10|issue = 4|pages = 484–491|doi = 10.1071/BI9570484|doi-access = free}}</ref> The computer simulation of the evolution by biologists became more common in the early 1960s, and the methods were described in books by Fraser and Burnell (1970)<ref>{{cite book|last1 = Fraser|first1 = Alex|author-link = Alex Fraser (scientist)|first2 = Donald|last2 = Burnell|year = 1970|title = Computer Models in Genetics|publisher = McGraw-Hill|location = New York|isbn = 978-0-07-021904-5}}</ref> and Crosby (1973).<ref>{{cite book|last = Crosby|first = Jack L.|year = 1973|title = Computer Simulation in Genetics|publisher = John Wiley & Sons|location = London|isbn = 978-0-471-18880-3}}</ref> Fraser's simulations included all of the essential elements of modern mutation-selection genetic particle algorithms.

From the mathematical viewpoint, the [[conditional distribution]] of the random states of a signal given some partial and noisy observations is described by a Feynman-Kac probability on the random trajectories of the signal weighted by a sequence of likelihood potential functions.<ref name="dp042" /><ref name="dmm002" /> [[Quantum Monte Carlo]], and more specifically [[Diffusion Monte Carlo|Diffusion Monte Carlo methods]] can also be interpreted as a mean-field genetic type particle approximation of Feynman-Kac path integrals.<ref name="dp042" /><ref name="dmm002" /><ref name="dmm00m2" /><ref name="h84">{{cite journal|last1 = Hetherington|first1 = Jack, H.|title = Observations on the statistical iteration of matrices|journal = Phys. Rev. A|date = 1984|volume = 30|issue = 2713|doi = 10.1103/PhysRevA.30.2713|pages = 2713–2719|bibcode=1984PhRvA..30.2713H}}</ref><ref name="dm-esaim032" /><ref name="caffarel1">{{cite journal|last1 = Assaraf|first1 = Roland|last2 = Caffarel|first2 = Michel|last3 = Khelif|first3 = Anatole|title = Diffusion Monte Carlo Methods with a fixed number of walkers|journal = Phys. Rev. E|url = http://qmcchem.ups-tlse.fr/files/caffarel/31.pdf|date = 2000|volume = 61|issue = 4|pages = 4566–4575|doi = 10.1103/physreve.61.4566|pmid = 11088257|bibcode = 2000PhRvE..61.4566A|url-status = dead|archive-url = https://web.archive.org/web/20141107015724/http://qmcchem.ups-tlse.fr/files/caffarel/31.pdf|archive-date = 2014-11-07}}</ref><ref name="caffarel2">{{cite journal|last1 = Caffarel|first1 = Michel|last2 = Ceperley|first2 = David|last3 = Kalos|first3 = Malvin|title = Comment on Feynman-Kac Path-Integral Calculation of the Ground-State Energies of Atoms|journal = Phys. Rev. Lett.|date = 1993|volume = 71|issue = 13|doi = 10.1103/physrevlett.71.2159|bibcode=1993PhRvL..71.2159C|pages=2159|pmid=10054598}}</ref> The origins of [[Quantum Monte Carlo]] methods are often attributed to [[Enrico Fermi]] and [[Robert D. Richtmyer|Robert Richtmyer]] who developed in 1948 a mean-field particle interpretation of [[Neutron chain reaction|neutron chain reactions]],<ref>{{cite journal|last1 = Fermi|first1 = Enrique|last2 = Richtmyer|first2 = Robert, D.|title = Note on census-taking in Monte Carlo calculations|journal = LAM|date = 1948|volume = 805|issue = A|url = http://scienze-como.uninsubria.it/bressanini/montecarlo-history/fermi-1948.pdf|quote = Declassified report Los Alamos Archive}}</ref> but the first heuristic-like and genetic type particle algorithm (a.k.a. Resampled or Reconfiguration Monte Carlo methods) for estimating ground state energies of quantum systems (in reduced matrix models) is due to Jack H. Hetherington in 1984.<ref name="h84" /> One can also quote the earlier seminal works of [[Ted Harris (mathematician)|Theodore E. Harris]] and [[Herman Kahn]] in particle physics, published in 1951, using mean-field but heuristic-like genetic methods for estimating particle transmission energies.<ref>{{cite journal|last1 = Herman|first1 = Kahn|last2 = Harris|first2 = Theodore, E.|title = Estimation of particle transmission by random sampling|journal = Natl. Bur. Stand. Appl. Math. Ser.|date = 1951|volume = 12|pages = 27–30|url = https://dornsifecms.usc.edu/assets/sites/520/docs/kahnharris.pdf}}</ref> In molecular chemistry, the use of genetic heuristic-like particle methodologies (a.k.a. pruning and enrichment strategies) can be traced back to 1955 with the seminal work of [[Marshall Rosenbluth|Marshall N. Rosenbluth]] and [[Arianna W. Rosenbluth]].<ref name=":5" />

The use of [[Genetic algorithm|genetic particle algorithms]] in advanced [[signal processing]] and [[Bayesian inference]] is more recent. In January 1993, Genshiro Kitagawa developed a "Monte Carlo filter",<ref name="Kitagawa1993">{{cite journal|last = Kitagawa|first = G.|date = January 1993|title=A Monte Carlo Filtering and Smoothing Method for Non-Gaussian Nonlinear State Space Models|journal =Proceedings of the 2nd U.S.-Japan Joint Seminar on Statistical Time Series Analysis|pages = 110–131|url=https://www.ism.ac.jp/~kitagawa/1993_US-Japan.pdf}}</ref> a slightly modified version of this article appeared in 1996.<ref>{{cite journal|last = Kitagawa|first = G.|year = 1996|title = Monte carlo filter and smoother for non-Gaussian nonlinear state space models|volume = 5|issue = 1|journal = Journal of Computational and Graphical Statistics|pages = 1–25|doi = 10.2307/1390750|jstor = 1390750}}
</ref> In April 1993, Neil J. Gordon et al., published in their seminal work<ref name="Gordon1993">{{Cite journal|title = Novel approach to nonlinear/non-Gaussian Bayesian state estimation| journal = IEE Proceedings F - Radar and Signal Processing |date = April 1993|issn = 0956-375X|pages = 107–113|volume = 140|issue = 2|first1 = N.J.|last1 = Gordon|first2 = D.J.|last2 = Salmond|first3 = A.F.M.|last3 = Smith|doi=10.1049/ip-f-2.1993.0015}}</ref> an application of genetic type algorithm in Bayesian statistical inference. The authors named their algorithm 'the bootstrap filter', and demonstrated that compared to other filtering methods, their bootstrap algorithm does not require any assumption about that state space or the noise of the system. Independently, the ones by Pierre Del Moral<ref name="dm962" /> and Himilcon Carvalho, Pierre Del Moral, [[Andrei Monin|André Monin]], and Gérard Salut<ref>{{cite journal|last1 = Carvalho|first1 = Himilcon|last2 = Del Moral|first2 = Pierre|last3 = Monin|first3 = André|last4 = Salut|first4 = Gérard|title = Optimal Non-linear Filtering in GPS/INS Integration.|journal = IEEE Transactions on Aerospace and Electronic Systems|date = July 1997|volume = 33|issue = 3|pages = 835|url = http://homepages.laas.fr/monin/Version_anglaise/Publications_files/GPS.pdf|bibcode = 1997ITAES..33..835C|doi = 10.1109/7.599254|s2cid = 27966240|access-date = 2015-06-01|archive-date = 2022-11-10|archive-url = https://web.archive.org/web/20221110053359/https://homepages.laas.fr/monin/Version_anglaise/Publications_files/GPS.pdf|url-status = dead}}</ref> on particle filters published in the mid-1990s. Particle filters were also developed in signal processing in early 1989-1992 by P. Del Moral, J.C. Noyer, G. Rigal, and G. Salut in the [[Laboratory for Analysis and Architecture of Systems|LAAS-CNRS]] in a series of restricted and classified research reports with STCAN (Service Technique des Constructions et Armes Navales), the IT company DIGILOG, and the [https://www.laas.fr/public/en LAAS-CNRS] (the Laboratory for Analysis and Architecture of Systems) on RADAR/SONAR and GPS signal processing problems.<ref>P. Del Moral, G. Rigal, and G. Salut. Estimation and nonlinear optimal control : An unified framework for particle solutions <br>
LAAS-CNRS, Toulouse, Research Report no. 91137, DRET-DIGILOG- LAAS/CNRS contract, April (1991).</ref><ref>P. Del Moral, G. Rigal, and G. Salut. Nonlinear and non-Gaussian particle filters applied to inertial platform repositioning.<br>
LAAS-CNRS, Toulouse, Research Report no. 92207, STCAN/DIGILOG-LAAS/CNRS Convention STCAN no. A.91.77.013, (94p.) September (1991).</ref><ref>P. Del Moral, G. Rigal, and G. Salut. Estimation and nonlinear optimal control : Particle resolution in filtering and estimation. Experimental results.<br>
Convention DRET no. 89.34.553.00.470.75.01, Research report no.2 (54p.), January (1992).</ref><ref>P. Del Moral, G. Rigal, and G. Salut. Estimation and nonlinear optimal control : Particle resolution in filtering and estimation. Theoretical results <br>
Convention DRET no. 89.34.553.00.470.75.01, Research report no.3 (123p.), October (1992).</ref><ref>P. Del Moral, J.-Ch. Noyer, G. Rigal, and G. Salut. Particle filters in radar signal processing : detection, estimation and air targets recognition.<br>
LAAS-CNRS, Toulouse, Research report no. 92495, December (1992).</ref><ref>P. Del Moral, G. Rigal, and G. Salut. Estimation and nonlinear optimal control : Particle resolution in filtering and estimation. <br>
Studies on: Filtering, optimal control, and maximum likelihood estimation. Convention DRET no. 89.34.553.00.470.75.01. Research report no.4 (210p.), January (1993).</ref>

=== Mathematical foundations ===
From 1950 to 1996, all the publications on particle filters, and genetic algorithms, including the pruning and resample Monte Carlo methods introduced in computational physics and molecular chemistry, present natural and heuristic-like algorithms applied to different situations without a single proof of their consistency, nor a discussion on the bias of the estimates and genealogical and ancestral tree-based algorithms.

The mathematical foundations and the first rigorous analysis of these particle algorithms are due to Pierre Del Moral<ref name="dm962" /><ref name=":22" /> in 1996. The article<ref name="dm962" /> also contains proof of the unbiased properties of a particle approximation of likelihood functions and unnormalized [[conditional probability]] measures. The unbiased particle estimator of the likelihood functions presented in this article is used today in Bayesian statistical inference.

Dan Crisan, Jessica Gaines, and [[Terry Lyons (mathematician)|Terry Lyons]],<ref name=":42">{{cite journal |last1=Crisan |first1=Dan |last2=Gaines |first2=Jessica |last3=Lyons |first3=Terry |date=1998 |title=Convergence of a branching particle method to the solution of the Zakai |journal=SIAM Journal on Applied Mathematics |volume=58 |issue=5 |pages=1568–1590 |doi=10.1137/s0036139996307371 |s2cid=39982562}}</ref><ref>{{cite journal |last1=Crisan |first1=Dan |last2=Lyons |first2=Terry |date=1997 |title=Nonlinear filtering and measure-valued processes |journal=Probability Theory and Related Fields |volume=109 |issue=2 |pages=217–244 |doi=10.1007/s004400050131 |s2cid=119809371 |doi-access=free}}</ref><ref>{{cite journal |last1=Crisan |first1=Dan |last2=Lyons |first2=Terry |date=1999 |title=A particle approximation of the solution of the Kushner–Stratonovitch equation |journal=Probability Theory and Related Fields |volume=115 |issue=4 |pages=549–578 |doi=10.1007/s004400050249 |s2cid=117725141 |doi-access=free}}</ref> as well as Pierre Del Moral, and Terry Lyons,<ref name=":52">{{cite journal |last1=Crisan |first1=Dan |last2=Del Moral |first2=Pierre |last3=Lyons |first3=Terry |date=1999 |title=Discrete filtering using branching and interacting particle systems |url=http://web.maths.unsw.edu.au/~peterdel-moral/crisan98discrete.pdf |journal=Markov Processes and Related Fields |volume=5 |issue=3 |pages=293–318}}</ref> created branching-type particle techniques with various population sizes around the end of the 1990s. P. Del Moral, A. Guionnet, and L. Miclo<ref name="dmm002" /><ref name="dg99" /><ref name="dg01" />  made more advances in this subject in 2000. Pierre Del Moral and Alice Guionnet<ref name=":2">{{Cite journal |last1=Del Moral |first1=P. |last2=Guionnet |first2=A. |date=1999 |title=Central limit theorem for nonlinear filtering and interacting particle systems |journal=The Annals of Applied Probability |volume=9 |issue=2 |pages=275–297 |doi=10.1214/aoap/1029962742 |issn=1050-5164 |doi-access=free}}</ref> proved the first central limit theorems in 1999, and Pierre Del Moral and Laurent Miclo<ref name="dmm002" /> proved them in 2000. The first uniform convergence results concerning the time parameter for particle filters were developed at the end of the 1990s by Pierre Del Moral and [[Alice Guionnet]].<ref name="dg99">{{cite journal|last1 = Del Moral|first1 = Pierre|last2 = Guionnet|first2 = Alice|title = On the stability of Measure Valued Processes with Applications to filtering|journal = C. R. Acad. Sci. Paris|date = 1999|volume = 39|issue = 1|pages = 429–434}}</ref><ref name="dg01">{{cite journal|last1 = Del Moral|first1 = Pierre|last2 = Guionnet|first2 = Alice|date = 2001|title = On the stability of interacting processes with applications to filtering and genetic algorithms|journal = Annales de l'Institut Henri Poincaré|volume = 37|issue = 2|pages = 155–194|bibcode=2001AIHPB..37..155D|doi = 10.1016/s0246-0203(00)01064-5|url = http://web.maths.unsw.edu.au/~peterdel-moral/ihp.ps|archive-url = https://web.archive.org/web/20141107004539/https://web.maths.unsw.edu.au/~peterdel-moral/ihp.ps|archive-date=2014-11-07}}</ref> The first rigorous analysis of genealogical tree-ased particle filter smoothers is due to P. Del Moral and L. Miclo in 2001<ref name=":4">{{Cite journal|title = Genealogies and Increasing Propagation of Chaos For Feynman-Kac and Genetic Models|journal = The Annals of Applied Probability|date = 2001|issn = 1050-5164|pages = 1166–1198|volume = 11|issue = 4|doi = 10.1214/aoap/1015345399|first1 = Pierre|last1 = Del Moral|first2 = Laurent|last2 = Miclo|doi-access = free}}</ref>

The theory on Feynman-Kac particle methodologies and related particle filter algorithms was developed in 2000 and 2004 in the books.<ref name="dmm002"/><ref name=":1" /> These abstract probabilistic models encapsulate genetic type algorithms, particle, and bootstrap filters, interacting Kalman filters (a.k.a. Rao–Blackwellized particle filter<ref name="rbpf1999">{{cite conference| citeseerx = 10.1.1.137.5199| title = Rao–Blackwellised particle filtering for dynamic Bayesian networks
| author = Doucet, A.
 |author2=De Freitas, N. |author3=Murphy, K. |author4=Russell, S.
| year          = 2000
| conference    = Proceedings of the Sixteenth conference on Uncertainty in artificial intelligence
| pages         = 176–183
}}
</ref>), importance sampling and resampling style particle filter techniques, including genealogical tree-based and particle backward methodologies for solving filtering and smoothing problems. Other classes of particle filtering methodologies include genealogical tree-based models,<ref name="dp13">{{cite book|last = Del Moral|first = Pierre|title = Mean field simulation for Monte Carlo integration|year = 2013|publisher = Chapman & Hall/CRC Press|quote = Monographs on Statistics & Applied Probability|url = http://www.crcpress.com/product/isbn/9781466504059|pages = 626}}</ref><ref name=":1" /><ref name=":3">{{cite journal|last1 = Del Moral|first1 = Pierre|last2 = Miclo|first2 = Laurent|title = Genealogies and Increasing Propagations of Chaos for Feynman-Kac and Genetic Models|journal = Annals of Applied Probability|date = 2001|volume = 11|issue = 4|pages = 1166–1198|url = http://web.maths.unsw.edu.au/~peterdel-moral/spc.ps}}</ref> backward Markov particle models,<ref name="dp13" /><ref name=":6">{{cite journal|last1 = Del Moral|first1 = Pierre|last2 = Doucet|first2 = Arnaud|last3 = Singh|first3 = Sumeetpal, S.|title = A Backward Particle Interpretation of Feynman-Kac Formulae|journal = M2AN|date = 2010|volume = 44|issue = 5|pages = 947–976|url = http://hal.inria.fr/docs/00/42/13/56/PDF/RR-7019.pdf|doi = 10.1051/m2an/2010048|s2cid = 14758161|doi-access = free}}</ref> adaptive mean-field particle models,<ref name=":0" /> island-type particle models,<ref>{{cite journal|last1 = Vergé|first1 = Christelle|last2 = Dubarry|first2 = Cyrille|last3 = Del Moral|first3 = Pierre|last4 = Moulines|first4 = Eric|title = On parallel implementation of Sequential Monte Carlo methods: the island particle model|journal = Statistics and Computing|date = 2013|doi = 10.1007/s11222-013-9429-x|volume = 25|issue = 2|pages = 243–260|arxiv = 1306.3911|bibcode = 2013arXiv1306.3911V|s2cid = 39379264}}</ref><ref>{{cite arXiv|last1 = Chopin|first1 = Nicolas|last2 = Jacob|first2 = Pierre, E.|last3 = Papaspiliopoulos|first3 = Omiros|title = SMC^2: an efficient algorithm for sequential analysis of state-space models|eprint=1101.1528v3|class = stat.CO|year = 2011}}</ref> particle Markov chain Monte Carlo methodologies,<ref>{{cite journal|last1 = Andrieu|first1 = Christophe|last2 = Doucet|first2 = Arnaud|last3 = Holenstein|first3 = Roman|title = Particle Markov chain Monte Carlo methods|journal = Journal of the Royal Statistical Society, Series B|date = 2010|volume = 72|issue = 3|pages = 269–342|doi = 10.1111/j.1467-9868.2009.00736.x|doi-access = free}}</ref><ref>{{cite arXiv|last1 = Del Moral|first1 = Pierre|last2 = Patras|first2 = Frédéric|last3 = Kohn|first3 = Robert|title = On Feynman-Kac and particle Markov chain Monte Carlo models|eprint=1404.5733|date = 2014|class = math.PR}}</ref> Sequential Monte Carlo samplers <ref>{{Cite journal |last1=Del Moral |first1=Pierre |last2=Doucet |first2=Arnaud |last3=Jasra |first3=Ajay |date=2006 |title=Sequential Monte Carlo Samplers |url=https://www.jstor.org/stable/3879283 |journal=Journal of the Royal Statistical Society. Series B (Statistical Methodology) |volume=68 |issue=3 |pages=411–436 |doi=10.1111/j.1467-9868.2006.00553.x |jstor=3879283 |issn=1369-7412|arxiv=cond-mat/0212648 }}</ref><ref>{{Cite journal |last=Peters |first=Gareth |date=2005 |title=Topics in Sequential Monte Carlo Samplers |url=https://www.ssrn.com/abstract=3785582 |journal=SSRN Electronic Journal |language=en |doi=10.2139/ssrn.3785582 |issn=1556-5068}}</ref><ref>{{Cite journal |last1=Del Moral |first1=Pierre |last2=Doucet |first2=Arnaud |last3=Peters |first3=Gareth |date=2004 |title=Sequential Monte Carlo Samplers CUED Technical Report |url=https://www.ssrn.com/abstract=3841065 |journal=SSRN Electronic Journal |language=en |doi=10.2139/ssrn.3841065 |issn=1556-5068}}</ref> and Sequential Monte Carlo Approximate Bayesian Computation methods<ref>{{Cite book |title=Handbook of approximate Bayesian computation |date=2019 |publisher=CRC Press, Taylor and Francis Group |isbn=978-1-315-11719-5 |editor-last=Sisson |editor-first=S. A. |location=Boca Raton |editor-last2=Fan |editor-first2=Y. |editor-last3=Beaumont |editor-first3=M. A.}}</ref> and Sequential Monte Carlo ABC based Bayesian Bootstrap.<ref>{{Cite journal |last1=Peters |first1=Gareth W. |last2=Wüthrich |first2=Mario V. |last3=Shevchenko |first3=Pavel V. |date=2010-08-01 |title=Chain ladder method: Bayesian bootstrap versus classical bootstrap |url=https://www.sciencedirect.com/science/article/pii/S0167668710000351 |journal=Insurance: Mathematics and Economics |volume=47 |issue=1 |pages=36–51 |doi=10.1016/j.insmatheco.2010.03.007 |issn=0167-6687|arxiv=1004.2548 }}</ref>

== The filtering problem ==

=== Objective ===
A particle filter's goal is to estimate the posterior density of state variables given observation variables. The particle filter is intended for use with a [[hidden Markov model|hidden Markov Model]], in which the system includes both hidden and observable variables. The observable variables (observation process) are linked to the hidden variables (state-process) via a known functional form. Similarly, the probabilistic description of the dynamical system defining the evolution of the state variables is known.

A generic particle filter estimates the posterior distribution of the hidden states using the observation measurement process. With respect to a state-space such as the one below:

:<math>\begin{array}{cccccccccc}
X_0&\to &X_1&\to &X_2&\to&X_3&\to &\cdots&\text{signal}\\
\downarrow&&\downarrow&&\downarrow&&\downarrow&&\cdots&\\
Y_0&&Y_1&&Y_2&&Y_3&&\cdots&\text{observation}
\end{array}</math>
 
the filtering problem is to estimate '''sequentially''' the values of the hidden states <math>X_k</math>, given the values of the observation process <math>Y_0,\cdots,Y_k,</math> at any time step ''k''.

All Bayesian estimates of <math>X_k</math> follow from the [[Posterior probability|posterior density]] <math>p(x_k|y_0,y_1,...,y_k)</math>. The particle filter methodology provides an approximation of these conditional probabilities using the empirical measure associated with a genetic type particle algorithm. In contrast, the Markov Chain Monte Carlo or [[importance sampling]] approach would model the full posterior <math>p(x_0,x_1,...,x_k|y_0,y_1,...,y_k)</math>.

=== The Signal-Observation model ===
Particle methods often assume <math>X_k</math> and the observations <math>Y_k</math> can be modeled in this form:

*<math>X_0, X_1, \cdots</math> is a [[Markov process]] on <math>\mathbb R^{d_x}</math> (for some <math>d_x\geqslant 1</math>) that evolves according to the transition probability density <math>p(x_k|x_{k-1})</math>. This model is also often written in a synthetic way as 
*:<math>X_k|X_{k-1}=x_k \sim p(x_k|x_{k-1})</math>
:with an initial probability density <math>p(x_0)</math>.
*The observations <math>Y_0, Y_1, \cdots</math>  take values in some state space on <math>\mathbb{R}^{d_y}</math> (for some <math>d_y\geqslant 1</math>) and are conditionally independent provided that <math>X_0, X_1, \cdots</math> are known. In other words, each <math>Y_k</math> only depends on <math>X_k</math>. In addition, we assume conditional distribution for <math>Y_k</math> given <math>X_k=x_k</math> are absolutely continuous, and in a synthetic way we have
*:<math>Y_k|X_k=y_k \sim p(y_k|x_k)</math>
An example of system with these properties is:

:<math>X_k = g(X_{k-1}) + W_{k-1}</math>
:<math>Y_k = h(X_k) + V_k</math>

where both <math>W_k</math> and <math>V_k</math> are mutually independent sequences with known [[probability density function]]s and ''g'' and ''h'' are known functions. These two equations can be viewed as [[state space (controls)|state space]] equations and look similar to the state space equations for the Kalman filter. If the functions ''g'' and ''h'' in the above example are linear, and if both <math>W_k</math> and <math>V_k</math> are [[Gaussian distribution|Gaussian]], the Kalman filter finds the exact Bayesian filtering distribution.  If not, Kalman filter-based methods are a first-order approximation ([[Extended Kalman filter|EKF]]) or a second-order approximation ([[Unscented Kalman filter|UKF]] in general, but if the probability distribution is Gaussian a third-order approximation is possible).

The assumption that the initial distribution and the transitions of the Markov chain are continuous for the [[Lebesgue measure]] can be relaxed. To design a particle filter we simply need to assume that we can sample the transitions <math>X_{k-1} \to X_k</math> of the Markov chain <math>X_k,</math> and to compute the likelihood function <math>x_k\mapsto p(y_k|x_k)</math> (see for instance the genetic selection mutation description of the particle filter given below). The continuous assumption on the Markov transitions of <math>X_k</math> is only used to derive in an informal (and rather abusive) way different formulae between posterior distributions using the Bayes' rule for conditional densities.

=== Approximate Bayesian computation models ===
{{Main|Approximate Bayesian computation}}
In certain problems, the conditional distribution of observations, given the random states of the signal, may fail to have a density; the latter may be impossible or too complex to compute.<ref name=":PFOBC"/> In this situation, an additional level of approximation is necessitated. One strategy is to replace the signal <math>X_k</math> by the Markov chain <math>\mathcal X_k=\left(X_k,Y_k\right)</math> and to introduce a virtual observation of the form

:<math>\mathcal Y_k=Y_k+\epsilon \mathcal V_k\quad\mbox{for some parameter}\quad\epsilon\in [0,1]</math>

for some sequence of independent random variables <math>\mathcal V_k</math> with known [[probability density function]]s. The central idea is to observe that

:<math>\text{Law}\left(X_k|\mathcal Y_0=y_0,\cdots, \mathcal Y_k=y_k\right)\approx_{\epsilon\downarrow 0} \text{Law}\left(X_k|Y_0=y_0,\cdots, Y_k=y_k\right)</math>

The particle filter associated with the Markov process <math>\mathcal X_k=\left(X_k,Y_k\right)</math> given the partial observations <math>\mathcal Y_0=y_0,\cdots, \mathcal Y_k=y_k,</math> is defined in terms of particles evolving in <math>\mathbb R^{d_x+d_y}</math> with a likelihood function given with some obvious abusive notation by <math>p(\mathcal Y_k|\mathcal X_k)</math>. These probabilistic techniques are closely related to [[Approximate Bayesian Computation]] (ABC). In the context of particle filters, these ABC particle filtering techniques were introduced in 1998 by P. Del Moral, J. Jacod and P. Protter.<ref>{{Cite journal|title = The Monte-Carlo method for filtering with discrete-time observations|journal = Probability Theory and Related Fields|date = 2001-07-01|issn = 0178-8051|pages = 346–368|volume = 120|issue = 3|doi = 10.1007/PL00008786|first1 = Pierre|last1 = Del Moral|first2 = Jean|last2 = Jacod|first3 = Philip|last3 = Protter|hdl = 1813/9179|s2cid = 116274|hdl-access = free}}</ref> They were further developed by P. Del Moral, A. Doucet and A. Jasra.<ref>{{Cite journal|title = An adaptive sequential Monte Carlo method for approximate Bayesian computation|journal = Statistics and Computing|date = 2011|issn = 0960-3174|pages = 1009–1020|volume = 22|issue = 5|doi = 10.1007/s11222-011-9271-y|first1 = Pierre|last1 = Del Moral|first2 = Arnaud|last2 = Doucet|first3 = Ajay|last3 = Jasra|citeseerx = 10.1.1.218.9800|s2cid = 4514922}}</ref><ref>{{Cite journal|title = Approximate Bayesian Computation for Smoothing|journal = Stochastic Analysis and Applications|date = May 4, 2014|issn = 0736-2994|pages = 397–420|volume = 32|issue = 3|doi = 10.1080/07362994.2013.879262|first1 = James S.|last1 = Martin|first2 = Ajay|last2 = Jasra|first3 = Sumeetpal S.|last3 = Singh|first4 = Nick|last4 = Whiteley|first5 = Pierre|last5 = Del Moral|first6 = Emma|last6 = McCoy|arxiv = 1206.5208|s2cid = 17117364}}</ref>

=== The nonlinear filtering equation ===
[[Bayes' Rule|Bayes' rule]] for conditional probability gives:

:<math>p(x_0, \cdots, x_k|y_0,\cdots,y_k) =\frac{p(y_0,\cdots,y_k|x_0, \cdots, x_k)  p(x_0,\cdots,x_k)}{p(y_0,\cdots,y_k)}</math>

where

:<math>\begin{align}
p(y_0,\cdots,y_k) &=\int p(y_0,\cdots,y_k|x_0,\cdots, x_k) p(x_0,\cdots,x_k) dx_0\cdots dx_k \\
p(y_0,\cdots, y_k|x_0,\cdots ,x_k) &=\prod_{l=0}^{k} p(y_l|x_l) \\
p(x_0,\cdots, x_k) &=p_0(x_0)\prod_{l=1}^{k} p(x_l|x_{l-1})
\end{align}</math>

Particle filters are also an approximation, but with enough particles they can be much more accurate.<ref name="dm962" /><ref name=":22" /><ref name=":1" /><ref name="dg99" /><ref name="dg01" /> The nonlinear filtering equation is given by the recursion

{{NumBlk|:|
<math>\begin{align} 
p(x_k|y_0,\cdots,y_{k-1}) &\stackrel{\text{updating}}{\longrightarrow} p(x_k|y_0,\cdots,y_k)=\frac{p(y_k|x_k)p(x_k|y_0,\cdots,y_{k-1})}{\int p(y_k|x'_k)p(x'_k|y_0,\cdots,y_{k-1})dx'_k}  \\
&\stackrel{\text{prediction}}{\longrightarrow}p(x_{k+1}|y_0,\cdots,y_k)=\int p(x_{k+1}|x_k) p(x_k|y_0,\cdots,y_k) dx_k
\end{align}</math>
|Eq. 1}}

with the convention <math>p(x_0|y_0,\cdots,y_{k-1})=p(x_0)</math> for ''k'' = 0. The nonlinear filtering problem consists in computing these conditional distributions sequentially.

=== Feynman-Kac formulation ===
{{Main|Feynman–Kac formula}}
We fix a time horizon n and a sequence of observations <math>Y_0=y_0,\cdots,Y_n=y_n</math>, and for each ''k'' = 0, ..., ''n'' we set:

:<math>G_k(x_k)=p(y_k|x_k).</math>

In this notation, for any bounded function ''F'' on the set of trajectories of <math>X_k</math> from the origin ''k'' = 0 up to time ''k'' = ''n'', we have the Feynman-Kac formula

:<math>\begin{align}
\int F(x_0,\cdots,x_n) p(x_0,\cdots,x_n|y_0,\cdots,y_n) dx_0\cdots dx_n &= \frac{\int F(x_0,\cdots,x_n) \left\{\prod\limits_{k=0}^{n} p(y_k|x_k)\right\}p(x_0,\cdots,x_n) dx_0\cdots dx_n}{\int \left\{\prod\limits_{k=0}^{n} p(y_k|x_k)\right\}p(x_0,\cdots,x_n) dx_0\cdots dx_n}\\
&=\frac{E\left(F(X_0,\cdots,X_n)\prod\limits_{k=0}^{n} G_k(X_k)\right)}{E\left(\prod\limits_{k=0}^{n} G_k(X_k)\right)}
\end{align}</math>

Feynman-Kac path integration models arise in a variety of scientific disciplines, including in computational physics, biology, information theory and computer sciences.<ref name="dmm002" /><ref name="dp13" /><ref name=":1" /> Their interpretations are dependent on the application domain. For instance, if we choose the indicator function <math>G_n(x_n)=1_A(x_n)</math> of some subset of the state space, they represent the conditional distribution of a Markov chain given it stays in a given tube; that is, we have:

:<math>E\left(F(X_0,\cdots,X_n) | X_0\in A, \cdots, X_n\in A\right) =\frac{E\left(F(X_0,\cdots,X_n)\prod\limits_{k=0}^{n} G_k(X_k)\right)}{E\left(\prod\limits_{k=0}^{n} G_k(X_k)\right)}</math>
and
:<math>P\left(X_0\in A,\cdots, X_n\in A\right)=E\left(\prod\limits_{k=0}^{n} G_k(X_k)\right)</math>

as soon as the normalizing constant is strictly positive.

== Particle filters ==

=== A Genetic type particle algorithm ===
Initially, such an algorithm starts with ''N'' independent random variables <math>\left(\xi^i_0\right)_{1\leqslant i\leqslant N}</math> with common probability density <math>p(x_0)</math>. The genetic algorithm selection-mutation transitions<ref name="dm962" /><ref name=":22" />

:<math>\xi_k:=\left(\xi^i_{k}\right)_{1\leqslant i\leqslant N}\stackrel{\text{selection}}{\longrightarrow} \widehat{\xi}_k:=\left(\widehat{\xi}^i_{k}\right)_{1\leqslant i\leqslant N}\stackrel{\text{mutation}}{\longrightarrow} \xi_{k+1}:=\left(\xi^i_{k+1}\right)_{1\leqslant i\leqslant N}</math>

mimic/approximate the updating-prediction transitions of the optimal filter evolution ({{EquationNote|Eq. 1}}):

* '''During the selection-updating transition''' we sample ''N'' (conditionally) independent random variables <math>\widehat{\xi}_k:=\left(\widehat{\xi}^i_{k}\right)_{1\leqslant i\leqslant N}</math> with common (conditional) distribution
::<math>\sum_{i=1}^N \frac{p(y_k|\xi^i_k)}{\sum_{j=1}^Np(y_k|\xi^j_k)} \delta_{\xi^i_k}(dx_k)</math>

where <math>\delta_a</math> stands for the '''[[Dirac measure]]''' at a given state a.

* '''During the mutation-prediction transition,''' from each selected particle <math>\widehat{\xi}^i_k</math> we sample independently a transition 
::<math>\widehat{\xi}^i_k \longrightarrow\xi^i_{k+1} \sim p(x_{k+1}|\widehat{\xi}^i_k), \qquad i=1,\cdots,N.</math>
In the above displayed formulae  <math>p(y_k|\xi^i_k)</math> stands for the likelihood function <math>x_k\mapsto p(y_k|x_k)</math> evaluated at <math>x_k=\xi^i_k</math>, and <math>p(x_{k+1}|\widehat{\xi}^i_k)</math> stands for the conditional density <math>p(x_{k+1}|x_k)</math> evaluated at <math>x_k=\widehat{\xi}^i_k</math>.

At each time ''k'', we have the particle approximations

:<math>\widehat{p}(dx_k|y_0,\cdots,y_k):=\frac{1}{N} \sum_{i=1}^N \delta_{\widehat{\xi}^i_k} (dx_k) \approx_{N\uparrow\infty} p(dx_k|y_0,\cdots,y_k) \approx_{N\uparrow\infty} 
\sum_{i=1}^N \frac{p(y_k|\xi^i_k)}{\sum_{i=1}^N p(y_k|\xi^j_k)} \delta_{\xi^i_k}(dx_k)</math>

and

:<math>\widehat{p}(dx_k|y_0,\cdots,y_{k-1}):=\frac{1}{N}\sum_{i=1}^N \delta_{\xi^i_k}(dx_k) \approx_{N\uparrow\infty} p(dx_k|y_0,\cdots,y_{k-1})</math>

In Genetic algorithms and [[Evolutionary computing]] community, the mutation-selection Markov chain described above is often called the genetic algorithm with proportional selection. Several branching variants, including with random population sizes have also been proposed in the articles.<ref name=":1" /><ref name=":42" /><ref name=":52" />

=== [[Monte Carlo method|Monte Carlo principles]] ===
Particle methods, like all sampling-based approaches (e.g., [[Markov chain Monte Carlo|Markov Chain Monte Carlo]]), generate a set of samples that approximate the filtering density

:<math>p(x_k|y_0, \cdots, y_k).</math>

For example, we may have ''N'' samples from the approximate posterior distribution of <math>X_k</math>, where the samples are labeled with superscripts as:

:<math>\widehat{\xi}_k^1, \cdots, \widehat{\xi}_k^{N}.</math>

Then, expectations with respect to the filtering distribution are approximated by

{{NumBlk|:| <math>\int f(x_k)p(x_k|y_0,\cdots,y_k) \, dx_k\approx_{N\uparrow\infty}\frac{1}{N} \sum_{i=1}^Nf\left(\widehat{\xi}_k^{i}\right)=\int f(x_k) \widehat{p}(dx_k|y_0,\cdots,y_k)</math>
|Eq. 2}}

with

:<math>\widehat{p}(dx_k|y_0,\cdots,y_k)=\frac{1}{N}\sum_{i=1}^N \delta_{\widehat{\xi}^i_k}(dx_k)</math>

where <math>\delta_a</math> stands for the '''[[Dirac measure]]''' at a given state a. The function ''f'', in the usual way for Monte Carlo, can give all the [[moment (mathematics)|moments]] etc. of the distribution up to some approximation error. When the approximation equation  ({{EquationNote|Eq. 2}}) is satisfied for any bounded function ''f'' we write

:<math>p(dx_k|y_0,\cdots,y_k):=p(x_k|y_0,\cdots,y_k) dx_k \approx_{N\uparrow\infty} \widehat{p}(dx_k|y_0,\cdots,y_k)=\frac{1}{N}\sum_{i=1}^N \delta_{\widehat{\xi}^{i}_k}(dx_k)</math>

Particle filters can be interpreted as a genetic type particle algorithm evolving with mutation and selection transitions. We can keep track of the ancestral lines

:<math>\left(\widehat{\xi}^{i}_{0,k}, \widehat{\xi}^{i}_{1,k},\cdots,\widehat{\xi}^{i}_{k-1,k},\widehat{\xi}^i_{k,k}\right)</math>

of the particles <math>i=1,\cdots,N</math>. The random states <math>\widehat{\xi}^{i}_{l,k}</math>, with the lower indices l=0,...,k, stands for the ancestor of the individual <math>\widehat{\xi}^{i}_{k,k}=\widehat{\xi}^i_k</math> at level l=0,...,k. In this situation, we have the approximation formula

{{NumBlk|:| <math>\begin{align}
\int F(x_0, \cdots,x_k) p(x_0,\cdots, x_k|y_0,\cdots,y_k) \, dx_0 \cdots dx_k &\approx_{N\uparrow\infty} \frac{1}{N} \sum_{i=1}^NF\left( \widehat{\xi}_{0,k}^{i}, \widehat{\xi}_{1,k}^{i}, \cdots, \widehat{\xi}_{k,k}^{i}\right) \\
& =\int F(x_0, \cdots, x_k)\widehat{p}(d(x_0, \cdots,x_k)|y_0,\cdots,y_k)
\end{align}</math> |Eq. 3}}

with the [[empirical measure]]

:<math>\widehat{p}(d(x_0,\cdots,x_k)|y_0,\cdots,y_k):=\frac{1}{N}\sum_{i=1}^N \delta_{\left(\widehat{\xi}^{i}_{0,k},\widehat{\xi}^{i}_{1,k},\cdots,\widehat{\xi}^{i}_{k,k}\right)}(d(x_0,\cdots,x_k))</math>

Here ''F'' stands for any founded function on the path space of the signal. In a more synthetic form ({{EquationNote|Eq. 3}}) is equivalent to

:<math>\begin{align}
p(d(x_0,\cdots,x_k)|y_0,\cdots,y_k)&:=p(x_0,\cdots,x_k|y_0,\cdots,y_k) \, dx_0\cdots dx_k \\
&\approx_{N\uparrow\infty} \widehat{p}(d(x_0,\cdots,x_k)|y_0,\cdots,y_k) \\
&:=\frac{1}{N}\sum_{i=1}^N \delta_{\left(\widehat{\xi}^{i}_{0,k}, \cdots,\widehat{\xi}^{i}_{k,k}\right)}(d(x_0,\cdots,x_k))
\end{align}</math>

Particle filters can be interpreted in many different ways. From the probabilistic point of view they coincide with a [[mean-field particle methods|mean-field particle]] interpretation of the nonlinear filtering equation. The updating-prediction transitions of the optimal filter evolution can also be interpreted as the classical genetic type selection-mutation transitions of individuals. The sequential importance resampling technique provides another interpretation of the filtering transitions coupling importance sampling with the bootstrap resampling step. Last, but not least, particle filters can be seen as an acceptance-rejection methodology equipped with a recycling mechanism.<ref name="dp13" /><ref name=":1" />

=== [[Mean-field particle methods|Mean-field particle simulation]] ===
{{Technical|section|date=June 2017}}

==== The general probabilistic principle ====
The nonlinear filtering evolution can be interpreted as a dynamical system in the set of probability measures of the form <math>\eta_{n+1}=\Phi_{n+1}\left(\eta_{n}\right)</math> where <math>\Phi_{n+1}</math> stands for some mapping from the set of probability distribution into itself. For instance, the evolution of the one-step optimal predictor <math> \eta_n(dx_n) =p(x_n|y_0,\cdots,y_{n-1})dx_n</math>

satisfies a nonlinear evolution starting with the probability distribution <math>\eta_0(dx_0)=p(x_0)dx_0</math>. One of the simplest ways to approximate these probability measures is to start with ''N'' independent random variables <math>\left(\xi^i_0\right)_{1\leqslant i\leqslant N}</math> with common probability distribution  <math>\eta_0(dx_0)=p(x_0)dx_0</math> . Suppose we have defined a sequence of ''N'' random variables <math>\left(\xi^i_n\right)_{1\leqslant i\leqslant N}</math> such that

:<math>\frac{1}{N}\sum_{i=1}^N \delta_{\xi^i_n}(dx_n) \approx_{N\uparrow\infty} \eta_n(dx_n)</math>

At the next step we sample ''N'' (conditionally) independent random variables <math>\xi_{n+1}:=\left(\xi^i_{n+1}\right)_{1\leqslant i\leqslant N}</math> with common law .

:<math>\Phi_{n+1}\left(\frac{1}{N}\sum_{i=1}^N \delta_{\xi^i_n}\right) \approx_{N\uparrow\infty} \Phi_{n+1}\left(\eta_{n}\right)=\eta_{n+1}</math>

==== A particle interpretation of the filtering equation ====
We illustrate this mean-field particle principle in the context of the evolution of the one step optimal predictors

{{NumBlk|:|
<math>p(x_{k}|y_0,\cdots,y_{k-1}) dx_k \to  p(x_{k+1}|y_0,\cdots,y_k)=\int p(x_{k+1}|x'_{k}) \frac{p(y_k|x_k') p(x'_k|y_0,\cdots,y_{k-1}) dx'_k}{\int p(y_k|x''_k) p(x''_k|y_0,\cdots,y_{k-1}) dx''_{k}}</math>
|Eq. 4}}

For ''k'' = 0 we use the convention <math>p(x_0|y_0,\cdots,y_{-1}):=p(x_0)</math>.

By the law of large numbers, we have

:<math>\widehat{p}(dx_0)=\frac{1}{N}\sum_{i=1}^N \delta_{\xi^{i}_0}(dx_0)\approx_{N\uparrow\infty} p(x_0)dx_0</math>

in the sense that

:<math>\int f(x_0)\widehat{p}(dx_0)=\frac{1}{N}\sum_{i=1}^N f(\xi^i_0)\approx_{N\uparrow\infty} \int f(x_0)p(dx_0)dx_0</math>

for any bounded function <math>f</math>. We further assume that we have constructed a sequence of particles <math>\left(\xi^i_k\right)_{1\leqslant i\leqslant N}</math> at some rank ''k'' such that

:<math>\widehat{p}(dx_k|y_0,\cdots,y_{k-1}):=\frac{1}{N}\sum_{i=1}^N \delta_{\xi^{i}_k}(dx_k)\approx_{N\uparrow\infty}~p(x_k~|~y_0,\cdots,y_{k-1})dx_k</math>

in the sense that for any bounded function <math>f</math> we have

:<math>\int f(x_k)\widehat{p}(dx_k|y_0,\cdots,y_{k-1})=\frac{1}{N}\sum_{i=1}^N f(\xi^i_k)\approx_{N\uparrow\infty} \int f(x_k)p(dx_k|y_0,\cdots,y_{k-1})dx_k</math>

In this situation, replacing <math id="{{EquationRef|1}}">p(x_k|y_0,\cdots,y_{k-1}) dx_k</math> by the [[empirical measure]] <math id="{{EquationRef|1}}">\widehat{p}(dx_k|y_0,\cdots,y_{k-1})</math> in the evolution equation of the one-step optimal filter stated in ({{EquationNote|Eq. 4}}) we find that

:<math>p(x_{k+1}|y_0,\cdots,y_k)\approx_{N\uparrow\infty} \int p(x_{k+1}|x'_{k}) \frac{p(y_k|x_k') \widehat{p}(dx'_k|y_0,\cdots,y_{k-1})}{ \int p(y_k|x''_k) \widehat{p}(dx''_k|y_0,\cdots,y_{k-1})}</math>

Notice that the right hand side in the above formula is a weighted probability mixture

:<math>\int p(x_{k+1}|x'_{k}) \frac{p(y_k|x_k') \widehat{p}(dx'_k|y_0,\cdots,y_{k-1})}{\int p(y_k|x''_k) \widehat{p}(dx''_k|y_0,\cdots,y_{k-1})}=\sum_{i=1}^N \frac{p(y_k|\xi^i_k)}{\sum_{i=1}^N p(y_k|\xi^j_k)} p(x_{k+1}|\xi^i_k)=:\widehat{q}(x_{k+1}|y_0,\cdots,y_k)</math>

where <math>p(y_k|\xi^i_k)</math> stands for the density <math>p(y_k|x_k)</math> evaluated at <math>x_k=\xi^i_k</math>, and <math>p(x_{k+1}|\xi^i_k)</math> stands for the density <math>p(x_{k+1}|x_k)</math> evaluated at <math>x_k=\xi^i_k</math> for <math>i=1,\cdots,N.</math>

Then, we sample ''N'' independent random variable <math>\left(\xi^i_{k+1}\right)_{1\leqslant i\leqslant N}</math> with common probability density <math>\widehat{q}(x_{k+1}|y_0,\cdots,y_k)</math>  so that

:<math>\widehat{p}(dx_{k+1}|y_0,\cdots,y_{k}):=\frac{1}{N}\sum_{i=1}^N \delta_{\xi^{i}_{k+1}}(dx_{k+1})\approx_{N\uparrow\infty} \widehat{q}(x_{k+1}|y_0,\cdots,y_{k}) dx_{k+1} \approx_{N\uparrow\infty} p(x_{k+1}|y_0,\cdots,y_{k})dx_{k+1}</math>

Iterating this procedure, we design a Markov chain such that

:<math>\widehat{p}(dx_k|y_0,\cdots,y_{k-1}):=\frac{1}{N}\sum_{i=1}^N \delta_{\xi^i_k}(dx_k) \approx_{N\uparrow\infty} p(dx_k|y_0,\cdots,y_{k-1}):=p(x_k|y_0,\cdots,y_{k-1}) dx_k</math>

Notice that the optimal filter is approximated at each time step k using the Bayes' formulae

:<math>p(dx_{k}|y_0,\cdots,y_{k}) \approx_{N\uparrow\infty} \frac{p(y_{k}|x_{k}) \widehat{p}(dx_{k}|y_0,\cdots,y_{k-1})}{\int p(y_{k}|x'_{k})\widehat{p}(dx'_{k}|y_0,\cdots,y_{k-1})}=\sum_{i=1}^N \frac{p(y_k|\xi^i_k)}{\sum_{j=1}^Np(y_k|\xi^j_k)}~\delta_{\xi^i_k}(dx_k)</math>

The terminology "mean-field approximation" comes from the fact that we replace at each time step the probability measure <math>p(dx_k|y_0,\cdots,y_{k-1})</math> by the empirical approximation <math>\widehat{p}(dx_k|y_0,\cdots,y_{k-1})</math>. The mean-field particle approximation of the filtering problem is far from being unique. Several strategies are developed in the books.<ref name="dp13" /><ref name=":1" />

=== Some convergence results ===
The analysis of the convergence of particle filters was started in 1996<ref name="dm962" /><ref name=":22" /> and in 2000 in the book<ref name="dmm002" /> and the series of articles.<ref name=":52" /><ref name="dg99" /><ref name="dg01" /><ref name=":2" /><ref name=":4" /><ref>{{Cite journal|title = Concentration inequalities for mean field particle models|journal = The Annals of Applied Probability|date = 2011|issn = 1050-5164|pages = 1017–1052|volume = 21|issue = 3|doi = 10.1214/10-AAP716|first1 = Pierre|last1 = Del Moral|first2 = Emmanuel|last2 = Rio|arxiv = 1211.1837|s2cid = 17693884}}</ref><ref>{{Cite book|title = On the Concentration Properties of Interacting Particle Processes|url = http://dl.acm.org/citation.cfm?id=2222549|publisher = Now Publishers Inc.|date = 2012|location = Hanover, MA, USA|isbn = 978-1601985125|first1 = Pierre|last1 = Del Moral|first2 = Peng|last2 = Hu|first3 = Liming|last3 = Wu}}</ref> More recent developments can be found in the books,<ref name="dp13" /><ref name=":1" /> When the filtering equation is stable (in the sense that it corrects any erroneous initial condition), the bias and the variance of the particle particle estimates

:<math>I_k(f):=\int f(x_k) p(dx_k|y_0,\cdots,y_{k-1}) \approx_{N\uparrow\infty} \widehat{I}_k(f):=\int f(x_k) \widehat{p}(dx_k|y_0,\cdots,y_{k-1})</math>

are controlled by the non asymptotic uniform estimates

:<math>\sup_{k\geqslant 0}\left\vert E\left(\widehat{I}_k(f)\right)-I_k(f)\right\vert\leqslant \frac{c_1}{N}</math>
:<math>\sup_{k\geqslant 0}E\left(\left[\widehat{I}_k(f)-I_k(f)\right]^2\right)\leqslant \frac{c_2}{N}</math>

for any function ''f'' bounded by 1, and for some finite constants <math>c_1,c_2.</math>  In addition, for any <math>x\geqslant 0</math>:

:<math>\mathbf{P} \left ( \left| \widehat{I}_k(f)-I_k(f)\right|\leqslant c_1 \frac{x}{N}+c_2 \sqrt{\frac{x}{N}}\land \sup_{0\leqslant k\leqslant n}\left| \widehat{I}_k(f)-I_k(f)\right|\leqslant c \sqrt{\frac{x\log(n)}{N}} \right ) > 1-e^{-x}</math>

for some finite constants <math>c_1, c_2</math> related to the asymptotic bias and variance of the particle estimate, and some finite constant ''c''. The same results are satisfied if we replace the one step optimal predictor by the optimal filter approximation.

== Genealogical trees and Unbiasedness properties ==
{{Technical|section|date=June 2017}}

=== Genealogical tree based particle smoothing ===
Tracing back in time the ancestral lines

:<math>\left(\widehat{\xi}^i_{0,k},\widehat{\xi}^i_{1,k},\cdots,\widehat{\xi}^i_{k-1,k},\widehat{\xi}^i_{k,k}\right), \quad \left(\xi^i_{0,k},\xi^i_{1,k},\cdots,\xi^i_{k-1,k},\xi^i_{k,k}\right)</math>

of the individuals <math>\widehat{\xi}^i_{k}\left(=\widehat{\xi}^i_{k,k}\right)</math> and <math>\xi^i_{k}\left(={\xi}^i_{k,k}\right)</math> at every time step ''k'', we also have the particle approximations

:<math>\begin{align}
\widehat{p}(d(x_0,\cdots,x_k)|y_0,\cdots,y_k) &:=\frac{1}{N}\sum_{i=1}^N \delta_{\left(\widehat{\xi}^i_{0,k},\cdots,\widehat{\xi}^i_{0,k}\right)}(d(x_0,\cdots,x_k)) \\
&\approx_{N\uparrow\infty} p(d(x_0,\cdots,x_k)|y_0,\cdots,y_k) \\
&\approx_{N\uparrow\infty} \sum_{i=1}^N \frac{p(y_k|\xi^i_{k,k})}{\sum_{j=1}^Np(y_k|\xi^j_{k,k})} \delta_{\left(\xi^i_{0,k},\cdots,\xi^i_{0,k}\right)}(d(x_0,\cdots,x_k)) \\
& \ \\
\widehat{p}(d(x_0,\cdots,x_k)|y_0,\cdots,y_{k-1}) &:=\frac{1}{N}\sum_{i=1}^N \delta_{\left(\xi^i_{0,k},\cdots,\xi^i_{k,k}\right)}(d(x_0,\cdots,x_k)) \\
&\approx_{N\uparrow\infty} p(d(x_0,\cdots,x_k)|y_0,\cdots,y_{k-1}) \\
&:=p(x_0,\cdots,x_k|y_0,\cdots,y_{k-1}) dx_0,\cdots,dx_k
\end{align}</math>

These empirical approximations are equivalent to the particle integral approximations

:<math>\begin{align}
\int F(x_0,\cdots,x_n) \widehat{p}(d(x_0,\cdots,x_k)|y_0,\cdots,y_k) &:=\frac{1}{N}\sum_{i=1}^N F\left(\widehat{\xi}^i_{0,k},\cdots,\widehat{\xi}^i_{0,k}\right) \\
&\approx_{N\uparrow\infty} \int F(x_0,\cdots,x_n) p(d(x_0,\cdots,x_k)|y_0,\cdots,y_k) \\
&\approx_{N\uparrow\infty} \sum_{i=1}^N \frac{p(y_k|\xi^i_{k,k})}{\sum_{j=1}^N p(y_k|\xi^j_{k,k})} F\left(\xi^i_{0,k}, \cdots,\xi^i_{k,k} \right) \\
& \ \\
\int F(x_0,\cdots,x_n) \widehat{p}(d(x_0,\cdots,x_k)|y_0,\cdots,y_{k-1}) &:=\frac{1}{N} \sum_{i=1}^N F\left(\xi^i_{0,k},\cdots,\xi^i_{k,k}\right) \\
&\approx_{N\uparrow\infty} \int F(x_0,\cdots,x_n) p(d(x_0,\cdots,x_k)|y_0,\cdots,y_{k-1})
\end{align}</math>

for any bounded function ''F'' on the random trajectories of the signal. As shown in<ref name=":3" /> the evolution of the genealogical tree coincides with a mean-field particle interpretation of the evolution equations associated with the posterior densities of the signal trajectories. For more details on these path space models, we refer to the books.<ref name="dp13" /><ref name=":1" />

=== Unbiased particle estimates of likelihood functions ===
We use the product formula

:<math>p(y_0,\cdots,y_n)=\prod_{k=0}^n p(y_k|y_0,\cdots,y_{k-1})</math>

with

:<math>p(y_k|y_0,\cdots,y_{k-1})=\int p(y_k|x_k) p(dx_k|y_0,\cdots,y_{k-1})</math>

and  the conventions <math>p(y_0|y_0,\cdots,y_{-1})=p(y_0)</math> and <math>p(x_0|y_0,\cdots,y_{-1})=p(x_0),</math> for ''k'' = 0. Replacing <math>p(x_k|y_0,\cdots,y_{k-1})dx_k</math> by the [[empirical measure|empirical]] approximation

:<math>\widehat{p}(dx_k|y_0,\cdots,y_{k-1}):=\frac{1}{N}\sum_{i=1}^N \delta_{\xi^i_k}(dx_k) \approx_{N\uparrow\infty} p(dx_k|y_0,\cdots,y_{k-1})</math>

in the above displayed formula, we design the following unbiased particle approximation of the likelihood function

:<math>p(y_0,\cdots,y_n) \approx_{N\uparrow\infty} \widehat{p}(y_0,\cdots,y_n)=\prod_{k=0}^n \widehat{p}(y_k|y_0,\cdots,y_{k-1}) </math>

with

:<math>\widehat{p}(y_k|y_0,\cdots,y_{k-1})=\int p(y_k|x_k) \widehat{p}(dx_k|y_0,\cdots,y_{k-1})=\frac{1}{N}\sum_{i=1}^N p(y_k|\xi^i_k)</math>

where <math>p(y_k|\xi^i_k)</math> stands for the density <math>p(y_k|x_k)</math> evaluated at <math>x_k=\xi^i_k</math>. The design of this particle estimate and the unbiasedness property has been proved in 1996 in the article.<ref name="dm962"/> Refined variance estimates can be found in<ref name=":1" /> and.<ref name="dp13" />

=== Backward particle smoothers ===
Using Bayes' rule, we have the formula

:<math>p(x_0,\cdots,x_n|y_0,\cdots,y_{n-1}) = p(x_n | y_0,\cdots,y_{n-1}) p(x_{n-1}|x_n, y_0,\cdots,y_{n-1} ) \cdots p(x_1|x_2,y_0,y_1) p(x_0|x_1,y_0)</math>

Notice that

:<math> \begin{align} 
p(x_{k-1}|x_{k},(y_0,\cdots,y_{k-1})) &\propto p(x_{k}|x_{k-1})p(x_{k-1}|(y_0,\cdots,y_{k-1})) \\
p(x_{k-1}|(y_0,\cdots,y_{k-1}) &\propto p(y_{k-1}|x_{k-1})p(x_{k-1}|(y_0,\cdots,y_{k-2})
\end{align}</math>

This implies that

:<math>p(x_{k-1}|x_k, (y_0,\cdots,y_{k-1}))=\frac{p(y_{k-1}|x_{k-1})p(x_{k}|x_{k-1})p(x_{k-1}|y_0,\cdots,y_{k-2})}{\int p(y_{k-1}|x'_{k-1})p(x_{k}|x'_{k-1})p(x'_{k-1}|y_0,\cdots,y_{k-2}) dx'_{k-1}}</math>

Replacing the one-step optimal predictors <math>p(x_{k-1}|(y_0,\cdots,y_{k-2}))dx_{k-1}</math> by the particle [[empirical measure]]s

:<math>\widehat{p}(dx_{k-1}|(y_0,\cdots,y_{k-2}))=\frac{1}{N}\sum_{i=1}^N \delta_{\xi^i_{k-1}}(dx_{k-1}) \left(\approx_{N\uparrow\infty} p(dx_{k-1}|(y_0,\cdots,y_{k-2})):={p}(x_{k-1}|(y_0,\cdots,y_{k-2})) dx_{k-1}\right)</math>

we find that

:<math>\begin{align}
p(dx_{k-1}| x_{k},(y_0,\cdots,y_{k-1})) &\approx_{N\uparrow\infty} \widehat{p}(dx_{k-1}|x_{k},(y_0,\cdots,y_{k-1})) \\
&:= \frac{p(y_{k-1}|x_{k-1}) p(x_{k}|x_{k-1}) \widehat{p}(dx_{k-1}|y_0,\cdots,y_{k-2})}{\int p(y_{k-1}|x'_{k-1})~p(x_{k}| x'_{k-1}) \widehat{p}(dx'_{k-1}|y_0,\cdots,y_{k-2})}\\
&= \sum_{i=1}^{N} \frac{p(y_{k-1}|\xi^i_{k-1}) p(x_{k}|\xi^i_{k-1})}{\sum_{j=1}^{N} p(y_{k-1}|\xi^j_{k-1}) p(x_{k}|\xi^j_{k-1})} \delta_{\xi^i_{k-1}}(dx_{k-1})
\end{align}</math>

We conclude that

:<math>p(d(x_0,\cdots,x_n)|(y_0,\cdots,y_{n-1})) \approx_{N\uparrow\infty} \widehat{p}_{backward}(d(x_0,\cdots,x_n)|(y_0,\cdots,y_{n-1}))</math>

with the backward particle approximation

:<math>\begin{align}
\widehat{p}_{backward} (d(x_0,\cdots,x_n)|(y_0,\cdots,y_{n-1})) = \widehat{p}(dx_n|(y_0,\cdots,y_{n-1})) \widehat{p}(dx_{n-1}|x_n,(y_0,\cdots,y_{n-1})) \cdots \widehat{p}(dx_1|x_2,(y_0,y_1)) \widehat{p}(dx_0|x_1,y_0)
\end{align}</math>

The probability measure

:<math>\widehat{p}_{backward}(d(x_0,\cdots,x_n)|(y_0,\cdots,y_{n-1}))</math>

is the probability of the random paths of a Markov chain <math>\left(\mathbb X^{\flat}_{k,n}\right)_{0\leqslant k\leqslant n}</math>running backward in time from time k=n to time k=0, and evolving at each time step k in the state space associated with the population of particles <math>\xi^i_k,  i=1,\cdots,N.</math>
* Initially (at time k=n) the chain <math>\mathbb X^{\flat}_{n,n}</math> chooses randomly a state with the distribution
::<math>\widehat{p}(dx_{n}|(y_0,\cdots,y_{n-1}))=\frac{1}{N}\sum_{i=1}^N \delta_{\xi^i_{n}}(dx_{n})</math>
* From time k to the time (k-1), the chain starting at some state <math>\mathbb X^{\flat}_{k,n}=\xi^i_k</math> for some <math> i=1,\cdots,N</math> at time k moves at time (k-1) to a random state <math>\mathbb{X}^{\flat}_{k-1,n}</math> chosen with the discrete weighted probability

:<math>\widehat{p}(dx_{k-1}|\xi^i_{k},(y_0,\cdots,y_{k-1}))= \sum_{j=1}^N\frac{p(y_{k-1}|\xi^j_{k-1}) p(\xi^i_{k}|\xi^j_{k-1})}{\sum_{l=1}^Np(y_{k-1}|\xi^l_{k-1}) p(\xi^i_{k}|\xi^l_{k-1})}~\delta_{\xi^j_{k-1}}(dx_{k-1})</math>

In the above displayed formula, <math>\widehat{p}(dx_{k-1}|\xi^i_{k},(y_0,\cdots,y_{k-1}))</math>  stands for the conditional distribution <math>\widehat{p}(dx_{k-1}|x_k, (y_0,\cdots,y_{k-1}))</math> evaluated at <math>x_k=\xi^i_{k}</math>. In the same vein, <math>p(y_{k-1}|\xi^j_{k-1})</math> and <math>p(\xi^i_k|\xi^j_{k-1})</math> stand for the conditional densities <math>p(y_{k-1}|x_{k-1})</math> and <math>p(x_k|x_{k-1})</math> evaluated at <math>x_k=\xi^i_{k}</math> and <math>x_{k-1}=\xi^j_{k-1}.</math> These models allows to reduce integration with respect to the densities <math>p((x_0,\cdots,x_n)|(y_0,\cdots,y_{n-1}))</math> in terms of matrix operations with respect to the Markov transitions of the chain described above.<ref name=":6" /> For instance, for any function <math>f_k</math> we have the particle estimates

:<math>\begin{align}
\int p(d(x_0,\cdots,x_n)&|(y_0,\cdots,y_{n-1}))f_k(x_k) \\
&\approx_{N\uparrow\infty} \int \widehat{p}_{backward}(d(x_0,\cdots,x_n)| (y_0,\cdots,y_{n-1})) f_k(x_k) \\
&=\int \widehat{p}(dx_n| (y_0,\cdots,y_{n-1})) \widehat{p}(dx_{n-1}|x_n,(y_0,\cdots,y_{n-1})) \cdots \widehat{p}(dx_k| x_{k+1},(y_0,\cdots,y_k)) f_k(x_k) \\
&=\underbrace{\left[\tfrac{1}{N},\cdots,\tfrac{1}{N}\right]}_{N \text{ times}}\mathbb{M}_{n-1} \cdots\mathbb M_{k} \begin{bmatrix} f_k(\xi^1_k)\\
\vdots\\ f_k(\xi^N_k) \end{bmatrix}
\end{align}</math>

where

:<math>\mathbb M_k= (\mathbb M_k(i,j))_{1\leqslant i,j\leqslant N}: \qquad \mathbb M_k(i,j)=\frac{p(\xi^i_{k}|\xi^j_{k-1})~p(y_{k-1}|\xi^j_{k-1})}{\sum\limits_{l=1}^{N} p(\xi^i_{k}|\xi^l_{k-1}) p(y_{k-1}|\xi^l_{k-1})}</math>

This also shows that if

:<math>\overline{F}(x_0,\cdots,x_n):=\frac{1}{n+1}\sum_{k=0}^n f_k(x_k)</math>

then

:<math>\begin{align} 
\int \overline{F}(x_0,\cdots,x_n) p(d(x_0,\cdots,x_n)|(y_0,\cdots,y_{n-1})) &\approx_{N\uparrow\infty} \int \overline{F}(x_0,\cdots,x_n) \widehat{p}_{backward}(d(x_0,\cdots,x_n)|(y_0,\cdots,y_{n-1})) \\
&=\frac{1}{n+1} \sum_{k=0}^n \underbrace{\left[\tfrac{1}{N},\cdots,\tfrac{1}{N}\right]}_{N \text{ times}}\mathbb M_{n-1}\mathbb M_{n-2}\cdots\mathbb{M}_k \begin{bmatrix} f_k(\xi^1_k)\\ \vdots\\ f_k(\xi^N_k) \end{bmatrix}
\end{align}</math>

=== Some convergence results ===
We shall assume that filtering equation is stable, in the sense that it corrects any erroneous initial condition.

In this situation, the '''particle approximations of the likelihood functions''' are unbiased and the relative variance is controlled by

:<math>E\left(\widehat{p}(y_0,\cdots,y_n)\right)= p(y_0,\cdots,y_n), \qquad E\left(\left[\frac{\widehat{p}(y_0,\cdots,y_n)}{p(y_0,\cdots,y_n)}-1\right]^2\right)\leqslant \frac{cn}{N},</math>

for some finite constant ''c''. In addition, for any <math>x\geqslant 0</math>:

:<math>\mathbf{P} \left ( \left\vert \frac{1}{n}\log{\widehat{p}(y_0,\cdots,y_n)}-\frac{1}{n}\log{p(y_0,\cdots,y_n)}\right\vert \leqslant c_1 \frac{x}{N}+c_2 \sqrt{\frac{x}{N}} \right ) > 1-e^{-x} </math>

for some finite constants <math>c_1, c_2</math> related to the asymptotic bias and variance of the particle estimate, and for some finite constant ''c''.

The bias and the variance of  '''the particle particle estimates based on the ancestral lines of the genealogical trees'''

:<math>\begin{align}
I^{path}_k(F) &:=\int F(x_0,\cdots,x_k) p(d(x_0,\cdots,x_k)|y_0,\cdots,y_{k-1}) \\
&\approx_{N\uparrow\infty} \widehat{I}^{path}_k(F) \\
&:=\int F(x_0,\cdots,x_k) \widehat{p}(d(x_0,\cdots,x_k)|y_0,\cdots,y_{k-1}) \\
&=\frac{1}{N}\sum_{i=1}^N F\left(\xi^i_{0,k},\cdots,\xi^i_{k,k}\right)
\end{align}</math>

are controlled by the non asymptotic uniform estimates

:<math>\left| E\left(\widehat{I}^{path}_k(F)\right)-I_k^{path}(F)\right|\leqslant \frac{c_1 k}{N}, \qquad E\left(\left[\widehat{I}^{path}_k(F)-I_k^{path}(F)\right]^2\right)\leqslant \frac{c_2 k}{N},</math>

for any function ''F'' bounded by 1, and for some finite constants <math>c_1, c_2.</math> In addition, for any <math>x\geqslant 0</math>:

:<math>\mathbf{P} \left ( \left|  \widehat{I}^{path}_k(F)-I_k^{path}(F)\right | \leqslant c_1 \frac{kx}{N}+c_2 \sqrt{\frac{kx}{N}} \land \sup_{0\leqslant k\leqslant n}\left| \widehat{I}_k^{path}(F)-I^{path}_k(F)\right| \leqslant c \sqrt{\frac{xn\log(n)}{N}} \right ) > 1-e^{-x}</math>

for some finite constants <math>c_1, c_2</math> related to the asymptotic bias and variance of the particle estimate, and for some finite constant ''c''. The same type of bias and variance estimates hold for the backward particle smoothers. For additive functionals of the form

:<math>\overline{F}(x_0,\cdots,x_n):=\frac{1}{n+1}\sum_{0\leqslant k\leqslant n}f_k(x_k)</math>

with

:<math>I^{path}_n(\overline{F}) \approx_{N\uparrow\infty} I^{\flat, path}_n(\overline{F}):=\int \overline{F}(x_0,\cdots,x_n) \widehat{p}_{backward}(d(x_0,\cdots,x_n)|(y_0,\cdots,y_{n-1}))</math>

with functions <math>f_k</math> bounded by 1, we have

:<math>\sup_{n\geqslant 0}{\left\vert E\left(\widehat{I}^{\flat,path}_n(\overline{F})\right)-I_n^{path}(\overline{F})\right\vert} \leqslant \frac{c_1}{N}</math>

and

:<math>E\left(\left[\widehat{I}^{\flat,path}_n(F)-I_n^{path}(F)\right]^2\right)\leqslant \frac{c_2}{nN}+ \frac{c_3}{N^2}</math>

for some finite constants <math>c_1,c_2,c_3.</math> More refined estimates including exponentially small probability of errors are developed in.<ref name="dp13" />

== Sequential Importance Resampling (SIR) ==

=== Monte Carlo filter and bootstrap filter ===
''Sequential importance [[Resampling (statistics)|Resampling]] (SIR)'', Monte Carlo filtering (Kitagawa 1993<ref name="Kitagawa1993"/>), bootstrap filtering algorithm (Gordon et al. 1993<ref name="Gordon1993"/>) and single distribution resampling (Bejuri W.M.Y.B et al. 2017<ref>{{Cite journal |last1=Bejuri |first1=Wan Mohd Yaakob Wan |last2=Mohamad |first2=Mohd Murtadha |last3=Raja Mohd Radzi |first3=Raja Zahilah |last4=Salleh |first4=Mazleena |last5=Yusof |first5=Ahmad Fadhil |date=2017-10-18 |title=Adaptive memory-based single distribution resampling for particle filter |journal=Journal of Big Data |volume=4 |issue=1 |pages=33 |doi=10.1186/s40537-017-0094-3 |s2cid=256407088 |issn=2196-1115|doi-access=free }}</ref>), are also commonly applied filtering algorithms, which approximate the filtering probability density <math>p(x_k|y_0,\cdots,y_k)</math> by a weighted set of ''N'' samples

: <math> \left \{ \left (w^{(i)}_k,x^{(i)}_k \right ) \ : \ i\in\{1,\cdots,N\} \right \}.</math>

The ''importance weights'' <math>w^{(i)}_k</math> are approximations to the relative posterior probabilities (or densities) of the samples such that

:<math>\sum_{i=1}^N w^{(i)}_k = 1.</math>

Sequential importance sampling (SIS) is a sequential (i.e., recursive) version of [[importance sampling]]. As in importance sampling, the expectation of a function ''f'' can be approximated as a weighted average

: <math> \int f(x_k) p(x_k|y_0,\dots,y_k) dx_k \approx \sum_{i=1}^N w_k^{(i)} f(x_k^{(i)}).</math>

For a finite set of samples, the algorithm performance is dependent on the choice of the ''proposal distribution''

: <math>\pi(x_k|x_{0:k-1},y_{0:k})\, </math>.

The "''optimal" proposal distribution'' is given as the ''target distribution''
: <math>\pi(x_k|x_{0:k-1},y_{0:k}) = p(x_k|x_{k-1},y_{k})=\frac{p(y_k|x_k)}{\int p(y_k|x_k)p(x_k|x_{k-1})dx_k}~p(x_k|x_{k-1}).</math>

This particular choice of proposal transition has been proposed by P. Del Moral in 1996 and 1998.<ref name=":22"/> When it is difficult to sample transitions according to the distribution  <math> p(x_k|x_{k-1},y_{k})</math> one natural strategy is to use the following particle approximation

:<math>\begin{align} 
\frac{p(y_k|x_k)}{\int p(y_k|x_k)p(x_k|x_{k-1})dx_k} p(x_k|x_{k-1})dx_k &\simeq_{N\uparrow\infty} \frac{p(y_k|x_k)}{\int p(y_k|x_k)\widehat{p}(dx_k|x_{k-1})} \widehat{p}(dx_k|x_{k-1}) \\
&= \sum_{i=1}^N \frac{p(y_k|X^i_k(x_{k-1}))}{\sum_{j=1}^N p(y_k|X^j_k(x_{k-1}))} \delta_{X^i_k(x_{k-1})}(dx_k)
\end{align}</math>

with the empirical approximation

:<math> \widehat{p}(dx_k|x_{k-1})= \frac{1}{N}\sum_{i=1}^{N} \delta_{X^i_k(x_{k-1})}(dx_k)~\simeq_{N\uparrow\infty} p(x_k|x_{k-1})dx_k </math>

associated with ''N'' (or any other large number of samples) independent random samples <math>X^i_k(x_{k-1}), i=1,\cdots,N </math>with the conditional distribution of the random state <math>X_k</math> given <math>X_{k-1}=x_{k-1}</math>. The consistency of the resulting particle filter of this approximation and other extensions are developed in.<ref name=":22"/> In the above display <math>\delta_a</math> stands for the '''[[Dirac measure]]''' at a given state a.

However, the transition prior probability distribution is often used as importance function, since it is easier to draw particles (or samples) and perform subsequent importance weight calculations:
: <math>\pi(x_k|x_{0:k-1},y_{0:k}) = p(x_k|x_{k-1}).</math>
''Sequential Importance Resampling'' (SIR) filters with transition prior probability distribution as importance function are commonly known as [[Resampling (statistics)#Bootstrap|bootstrap filter]] and [[condensation algorithm]].

''Resampling'' is used to avoid the problem of the degeneracy of the algorithm, that is, avoiding the situation that all but one of the importance weights are close to zero. The performance of the algorithm can be also affected by proper choice of resampling method. The ''[[stratified sampling]]'' proposed by Kitagawa (1993<ref name="Kitagawa1993"/>) is optimal in terms of variance.

A single step of sequential importance resampling is as follows:

:1) For <math>i=1,\cdots,N</math> draw samples from the ''proposal distribution''
:: <math>x^{(i)}_k \sim \pi(x_k|x^{(i)}_{0:k-1},y_{0:k})</math>

:2) For <math>i=1,\cdots,N</math> update the importance weights up to a normalizing constant:
::<math>\hat{w}^{(i)}_k = w^{(i)}_{k-1} \frac{p(y_k|x^{(i)}_k) p(x^{(i)}_k|x^{(i)}_{k-1})} {\pi(x_k^{(i)}|x^{(i)}_{0:k-1},y_{0:k})}.</math>
: Note that when we use the transition prior probability distribution as the importance function, 
::<math> \pi(x_k^{(i)}|x^{(i)}_{0:k-1},y_{0:k}) = p(x^{(i)}_k|x^{(i)}_{k-1}),</math>
:this simplifies to the following :
::<math> \hat{w}^{(i)}_k = w^{(i)}_{k-1} p(y_k|x^{(i)}_k), </math>

:3) For <math>i=1,\cdots,N</math> compute the normalized importance weights:
:: <math>w^{(i)}_k = \frac{\hat{w}^{(i)}_k}{\sum_{j=1}^N \hat{w}^{(j)}_k}</math>

:4) Compute an estimate of the effective number of particles as
:: <math>\hat{N}_\mathit{eff} = \frac{1}{\sum_{i=1}^N\left(w^{(i)}_k\right)^2} </math>
:This criterion reflects the variance of the weights. Other criteria can be found in the article,<ref name=":0"/> including their rigorous analysis and central limit theorems.

:5) If the effective number of particles is less than a given threshold <math>\hat{N}_\mathit{eff} < N_{thr}</math>, then perform resampling:
::a) Draw ''N'' particles from the current particle set with probabilities proportional to their weights. Replace the current particle set with this new one.
::b) For <math>i=1,\cdots,N</math> set <math>w^{(i)}_k = 1/N.</math>

The term "Sampling Importance Resampling" is also sometimes used when referring to SIR filters, but the term ''Importance Resampling'' is more accurate because the word "resampling" implies that the initial sampling has already been done.<ref name="bda">{{Cite book|last1=Gelman|first1=Andrew|title=Bayesian Data Analysis, Third Edition|last2=Carlin|first2=John B.|last3=Stern|first3=Hal S.|last4=Dunson|first4=David B.|last5=Vehtari|first5=Aki|last6=Rubin|first6=Donald B.|publisher=Chapman and Hall/CRC|year=2013|isbn=978-1-4398-4095-5|author-link1=Andrew Gelman|author-link2=John Carlin (professor)|author-link6=Donald Rubin}}</ref>

=== Sequential importance sampling (SIS) ===
* Is the same as sequential importance resampling, but without the resampling stage.

=== "Direct version" algorithm ===
{{confusing section|date=October 2011}}
The "direct version" algorithm {{citation needed|date=October 2011}} is rather simple (compared to other particle filtering algorithms) and it uses composition and rejection. To generate a single sample ''x'' at ''k'' from <math>p_{x_k|y_{1:k}}(x|y_{1:k})</math>:
:1) Set ''n'' ''= 0'' (This will count the number of particles generated so far)

:2) [[Uniform distribution (discrete)|Uniformly]] choose an index i from the range <math>\{1,..., N\}</math>

:3) Generate a test <math>\hat{x}</math> from the distribution <math>p(x_k|x_{k-1})</math> with <math> x_{k-1}=x_{k-1|k-1}^{(i)}</math>

:4) Generate the probability of <math>\hat{y}</math> using <math>\hat{x}</math> from <math>p(y_k|x_k),~\mbox{with}~x_k=\hat{x}</math> where <math>y_k</math> is the measured value

:5) Generate another [[Uniform distribution (continuous)|uniform]] u from <math>[0, m_k]</math> where <math>m_k = \sup_{x_k} p(y_k|x_k) </math>

:6) Compare u and <math>p\left(\hat{y}\right)</math>

::6a) If u is larger then repeat from step 2

::6b) If u is smaller then save <math>\hat{x}</math> as <math>x_{k|k}^{(i)}</math> and increment n

:7) If ''n == N'' then quit

The goal is to generate P "particles" at ''k'' using only the particles from <math>k-1</math>. This requires that a Markov equation can be written (and computed) to generate a <math>x_k</math> based only upon <math>x_{k-1}</math>. This algorithm uses the composition of the P particles from <math>k-1</math> to generate a particle at ''k'' and repeats (steps 2–6) until P particles are generated at ''k''.

This can be more easily visualized if ''x'' is viewed as a two-dimensional array. One dimension is ''k'' and the other dimension is the particle number. For example, <math>x(k,i)</math> would be the i<sup>th</sup> particle at <math>k</math> and can also be written <math>x_k^{(i)}</math> (as done above in the algorithm). Step 3 generates a ''potential'' <math>x_k</math> based on a randomly chosen particle (<math>x_{k-1}^{(i)}</math>) at time <math>k-1</math> and rejects or accepts it in step 6. In other words, the <math>x_k</math> values are generated using the previously generated <math>x_{k-1}</math>.

== Applications ==
Particle filters and Feynman-Kac particle methodologies find application in several contexts, as an effective mean for tackling noisy observations or strong nonlinearities, such as:
*[[Bayesian inference]], [[machine learning]], [[Rare Event Sampling|risk analysis and rare event sampling]]
*[[Bioinformatics]]<ref name=":PFOBC"/>
*[[Computational science]]
*[[Economics]], [[financial mathematics]] and [[mathematical finance]]: particle filters can perform simulations which are needed to compute the high-dimensional and/or complex integrals related to problems such as dynamic stochastic general equilibrium models in macro-economics and option pricing<ref>{{cite journal|doi=10.1080/07474938.2011.607333|title=A Survey of Sequential Monte Carlo Methods for Economics and Finance|journal=Econometric Reviews|last=Creal|first=Drew|volume=31|issue=2|year=2012|pages=245–296 |s2cid=2730761 |url=https://research.vu.nl/en/publications/991e471a-a074-42a1-8206-0fbef56a3d93 |hdl=1871/15287|hdl-access=free}}</ref>
*[[Engineering]]
*Infectious disease [[epidemiology]] where they have been applied to a number of epidemic forecasting problems, for example predicting seasonal influenza epidemics<ref>{{cite journal | last1 = Moss | first1 = Robert | last2 = Zarebski | first2 = Alexander | last3 = Dawson | first3 = Peter | last4 = McCaw | first4 = James M.| title = Forecasting influenza outbreak dynamics in Melbourne from Internet search query surveillance data| journal = Influenza and Other Respiratory Viruses| volume = 10| issue = 4| pages = 314–323| year = 2016| doi = 10.1111/irv.12376 | doi-access = free | pmid = 26859411 | pmc = 4910172 }}</ref>
*[[Fault detection and isolation]]: in observer-based schemas a particle filter can forecast expected sensors output enabling fault isolation<ref>{{cite journal|doi=10.1109/TIE.2015.2399396|title=Intelligent Particle Filter and Its Application to Fault Detection of Nonlinear System|journal= IEEE Transactions on Industrial Electronics|volume=62|issue=6|year=2015|last1=Shen|first1=Yin|last2=Xiangping|first2=Zhu|page=1 |s2cid=23951880 }}</ref><ref>{{cite journal|doi=10.3390/s21093066 |title=A Particle Filtering Approach for Fault Detection and Isolation of UAV IMU Sensors: Design, Implementation and Sensitivity Analysis |journal=Sensors|volume=21|issue=9|year=2021|last1=D'Amato|first1=Edigio|last2=Notaro|first2=Immacolata|last3=Nardi|first3=Vito Antonio|last4=Scordamaglia|first4=Valerio|page=3066 |pmid=33924891 |pmc=8124649 |bibcode=2021Senso..21.3066D |doi-access=free }}</ref><ref>{{cite journal|doi=10.1080/00207720110102566|title=Particle filtering-based fault detection in non-linear stochastic systems|journal= International Journal of Systems Science|volume=33|issue=4|year=2002|first1=V.|last1=Kadirkamanathan|first2=P.|last2=Li|first3=M. H.|last3=Jaward|first4=S. G.|last4=Fabri|pages=259–265 |s2cid=28634585 }}</ref>
*[[Molecular chemistry]] and [[computational physics]]
*[[Pharmacokinetics]]<ref>Bonate P: Pharmacokinetic-Pharmacodynamic Modeling and Simulation. Berlin: Springer; 2011.</ref>
*[[Phylogenetics]]
*[[Robotics]], [[artificial intelligence]]: [[Monte Carlo localization]] is a de facto standard in mobile robot localization<ref name="aaai1999">
Dieter Fox, Wolfram Burgard, Frank Dellaert, and Sebastian Thrun, "[http://www.cs.washington.edu/ai/Mobile_Robotics/abstracts/sampling-aaai-99.abstract.html Monte Carlo Localization: Efficient Position Estimation for Mobile Robots]." ''Proc. of the Sixteenth National Conference on Artificial Intelligence'' John Wiley & Sons Ltd, 1999.</ref><ref name="pr">
Sebastian Thrun, Wolfram Burgard, Dieter Fox. [http://www.probabilistic-robotics.org/ ''Probabilistic Robotics''] MIT Press, 2005. Ch. 8.3 {{ISBN|9780262201629}}.</ref><ref name="robust">Sebastian Thrun, Dieter Fox, Wolfram Burgard, Frank Dellaert. "[http://robots.stanford.edu/papers/thrun.robust-mcl.html Robust monte carlo localization for mobile robots]." ''Artificial Intelligence'' 128.1 (2001): 99–141.
</ref>
*[[Signal processing|Signal and image processing]]: visual localization, tracking, [[feature (computer vision)|feature]] recognition<ref>{{cite journal | url=https://link.springer.com/article/10.1007/s10723-019-09502-1 | doi=10.1007/s10723-019-09502-1 | title=A Robust and Accurate Particle Filter-Based Pupil Detection Method for Big Datasets of Eye Video | year=2020 | last1=Abbasi | first1=Mahdi | last2=Khosravi | first2=Mohammad R. | journal=Journal of Grid Computing | volume=18 | issue=2 | pages=305–325 | s2cid=209481431 }}</ref>

== Other particle filters ==
* [[Auxiliary particle filter]]<ref name="apf1999">{{cite journal
 | author = Pitt, M.K.
 | author2 = Shephard, N.
 | year = 1999
 | title = Filtering Via Simulation: Auxiliary Particle Filters
 | journal = Journal of the American Statistical Association
 | volume = 94
 | issue = 446
 | pages = 590–591
 | url = https://www.questia.com/PM.qst?a=o&se=gglsc&d=5002321997
 | access-date = 2008-05-06
 | doi = 10.2307/2670179
 | jstor = 2670179
 | archive-date = 2007-10-16
 | archive-url = https://web.archive.org/web/20071016200646/http://www.questia.com/PM.qst?a=o
 | url-status = dead
 }}</ref>
* Cost Reference particle filter
* [[Exponential Natural Particle Filter]]<ref name="xnpf2015">{{cite arXiv
 | author = Zand, G.
 | author2= Taherkhani, M. |author3=Safabakhsh, R. 
 | year = 2015
 | title = Exponential Natural Particle Filter
 | eprint = 1511.06603
| class= cs.LG }}</ref>
* Feynman-Kac and mean-field particle methodologies<ref name="dm962"/><ref name="dp13" /><ref name=":1" />
* Gaussian particle filter
* Gauss–Hermite particle filter
* Hierarchical/Scalable particle filter<ref name="Canton2011">{{cite journal
 | author = Canton-Ferrer, C.
 |author2=Casas, J.R. |author3=Pardàs, M. 
 | year = 2011
 | title = Human Motion Capture Using Scalable Body Models
 | journal = Computer Vision and Image Understanding
 | volume = 115
 | issue = 10
 | pages = 1363–1374
 | doi = 10.1016/j.cviu.2011.06.001
 |hdl=2117/13393 }}</ref>
* Nudged particle filter<ref>{{Cite journal|last1=Akyildiz|first1=Ömer Deniz|last2=Míguez|first2=Joaquín|date=2020-03-01|title=Nudging the particle filter|journal=Statistics and Computing|language=en|volume=30|issue=2|pages=305–330|doi=10.1007/s11222-019-09884-y|s2cid=88515918|issn=1573-1375|doi-access=free|hdl=10044/1/100011|hdl-access=free}}</ref>
* Particle Markov-Chain Monte-Carlo, see e.g. [[pseudo-marginal Metropolis–Hastings algorithm]].
* Rao–Blackwellized particle filter<ref name="rbpf1999"/>
* [[Regularized auxiliary particle filter]]<ref name="jliu2011">{{cite journal
 | author = Liu, J.
 |author2=Wang, W. |author3=Ma, F. 
 | year = 2011
 | title = A Regularized Auxiliary Particle Filtering Approach for System State Estimation and Battery Life Prediction
 | journal = Smart Materials and Structures
 | volume = 20
 | issue = 7
 | pages = 1–9
 | doi = 10.1088/0964-1726/20/7/075021
| bibcode = 2011SMaS...20g5021L|s2cid=110670991 |url=https://escholarship.org/uc/item/0131z9gj }}</ref>
* [[Rejection sampling|Rejection-sampling]] based optimal particle filter<ref name="optrj2008">{{cite conference
| citeseerx           = 10.1.1.190.7092
| title         = An Optimal Filtering Algorithm for Non-Parametric Observation Models in Robot Localization
| author        = Blanco, J.L. |author2=Gonzalez, J. |author3=Fernandez-Madrigal, J.A.
| year          = 2008
| conference    = IEEE International Conference on Robotics and Automation (ICRA'08)
| pages         = 461–466
}}
</ref><ref name="optrj2010">{{cite journal
| title         = Optimal Filtering for Non-Parametric Observation Models: Applications to Localization and SLAM
| author        = Blanco, J.L. |author2=Gonzalez, J. |author3=Fernandez-Madrigal, J.A.
| year          = 2010
| journal       = The International Journal of Robotics Research
| volume        = 29
| number        = 14
| pages         = 1726–1742
| doi           = 10.1177/0278364910364165
| citeseerx         = 10.1.1.1031.4931
| s2cid = 453697 }}
</ref>
* Unscented particle filter

== See also ==
* [[Ensemble Kalman filter]]
* [[Generalized filtering]]
* [[Genetic algorithm]]
* [[Mean-field particle methods]]
* [[Monte Carlo localization]]
* [[Moving horizon estimation]]
* [[Recursive Bayesian estimation]]

== References ==
{{Reflist}}

== Bibliography ==
* {{cite journal | last1 = Del Moral | first1 = Pierre | year = 1996 | title = Non Linear Filtering: Interacting Particle Solution | url = http://web.maths.unsw.edu.au/~peterdel-moral/mprfs.pdf | journal = Markov Processes and Related Fields | volume = 2 | issue = 4 | pages = 555–580 | access-date = 2015-05-31 | archive-date = 2016-03-04 | archive-url = https://web.archive.org/web/20160304052857/http://web.maths.unsw.edu.au/~peterdel-moral/mprfs.pdf | url-status = dead }}
* Del Moral, Pierre (2004). ''[https://www.springer.com/us/book/9780387202686#reviews Feynman-Kac formulae. Genealogical and interacting particle approximations]''. Springer. p.&nbsp;575. "Series: Probability and Applications"
* Del Moral, Pierre (2013). ''[https://www.crcpress.com/product/isbn/9781466504059 Mean field simulation for Monte Carlo integration]''[https://www.crcpress.com/product/isbn/9781466504059 .] Chapman & Hall/CRC Press. p.&nbsp;626. "Monographs on Statistics & Applied Probability"
* {{cite book
 | author = Cappe, O. |author2=Moulines, E. |author3=Ryden, T.
 | year = 2005
 | title = Inference in Hidden Markov Models
 | publisher = Springer
}}
* {{cite book
 | author = Liu, J.S.
 | year = 2001
 | title = Monte Carlo strategies in Scientific Computing
 | publisher = Springer
}}
*{{cite journal
 | author = Kong, A.
 |author2=Liu, J.S. |author3=Wong, W.H. 
 | year = 1994
 | title = Sequential imputations and Bayesian missing data problems
 | journal = Journal of the American Statistical Association
 | volume = 89
 | issue = 425
 | pages = 278–288
 | url = http://www.people.fas.harvard.edu/~junliu/TechRept/94folder/klw94.pdf
 | doi = 10.1080/01621459.1994.10476469
}}
*{{cite journal
 | author = Liu, J.S.
 |author2=Chen, R.
 | year = 1995
 | title = Blind deconvolution via sequential imputations
 | journal = Journal of the American Statistical Association
 | volume = 90
 | issue = 430
 | pages = 567–576
 | url = http://www.people.fas.harvard.edu/~junliu/TechRept/95folder/liu&chen95_s.pdf
 | doi = 10.2307/2291068
|jstor=2291068
 }}
* {{cite book
 | author = Ristic, B. |author2=Arulampalam, S. |author3=Gordon, N.
 | year = 2004
 | title = Beyond the Kalman Filter: Particle Filters for Tracking Applications
 | publisher = Artech House
}}
* {{cite journal
 | author = Doucet, A.
 |author2=Johansen, A.M.
 | date = December 2008
 | title = A tutorial on particle filtering and smoothing: fifteen years later
 | journal = Technical Report
 | url = http://www.cs.ubc.ca/%7Earnaud/doucet_johansen_tutorialPF.pdf
}}
* {{cite journal
 | author = Doucet, A. |author2=Godsill, S. |author3=Andrieu, C.
 | year = 2000
 | title = On sequential Monte Carlo sampling methods for Bayesian filtering
 | journal = Statistics and Computing
 | volume = 10
 | issue = 3
 | pages = 197–208
 | doi = 10.1023/A:1008935410038
|s2cid=16288401 }}
* {{cite journal
 | author = Arulampalam, M.S. |author2=Maskell, S. |author3=Gordon, N. |author4=Clapp, T.
 | year = 2002
 | title = A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking
 | journal = IEEE Transactions on Signal Processing
 | volume = 50
 | issue = 2
 | pages = 174–188
 | doi = 10.1109/78.978374 
| bibcode = 2002ITSP...50..174A|citeseerx=10.1.1.471.8617 |s2cid=55577025 }}
* {{cite journal
 | author = Cappe, O. |author2=Godsill, S. |author3=Moulines, E.
 | year = 2007
 | title = An overview of existing methods and recent advances in sequential Monte Carlo
 | journal = Proceedings of the IEEE
 | volume = 95
 | issue = 5
 | doi = 10.1109/JPROC.2007.893250
 | pages = 899–924
|s2cid=3081664 }}
* {{cite journal
 | author = Kitagawa, G.
 | year = 1996
 | title =Monte carlo filter and smoother for non-Gaussian nonlinear state space models
 | volume = 5
 | issue = 1
 | journal = Journal of Computational and Graphical Statistics
 | pages = 1–25
 | doi = 10.2307/1390750
 | jstor = 1390750
}}
* {{cite journal
 | author = Kotecha, J.H.
 |author2=Djuric, P.
 | year = 2003
 | title =Gaussian Particle filtering
 | volume = 51
 | issue = 10
 | journal = IEEE Transactions on Signal Processing
|page=2592
 |doi=10.1109/TSP.2003.816758
 |bibcode=2003ITSP...51.2592K
 }}
* {{cite journal
 | author = Haug, A.J.
 | year = 2005
 | title = A Tutorial on Bayesian Estimation and Tracking Techniques Applicable to Nonlinear and Non-Gaussian Processes
 | url = https://apps.dtic.mil/sti/pdfs/AD1125123.pdf
 | archive-url = https://web.archive.org/web/20211222173929/https://apps.dtic.mil/sti/pdfs/AD1125123.pdf
 | url-status = live
 | archive-date = December 22, 2021
 | access-date = 2021-12-22
 | journal = The MITRE Corporation, USA, Tech. Rep., Feb
}}
* {{cite journal
 | author = Pitt, M.K.
 | author2 = Shephard, N.
 | year = 1999
 | title = Filtering Via Simulation: Auxiliary Particle Filters
 | journal = Journal of the American Statistical Association
 | volume = 94
 | issue = 446
 | pages = 590–591
 | url = https://www.questia.com/PM.qst?a=o&se=gglsc&d=5002321997
 | access-date = 2008-05-06
 | doi = 10.2307/2670179
 | jstor = 2670179
 | archive-date = 2007-10-16
 | archive-url = https://web.archive.org/web/20071016200646/http://www.questia.com/PM.qst?a=o
 | url-status = dead
 }}
* {{cite journal
 | author = Gordon, N. J. |author2=Salmond, D. J. |author3=Smith, A. F. M.
 | year = 1993
 | title = Novel approach to nonlinear/non-Gaussian Bayesian state estimation
 | journal =  IEE Proceedings F - Radar and Signal Processing
 | volume = 140
 | issue = 2
 | pages = 107–113
 | doi = 10.1049/ip-f-2.1993.0015
}}
* {{cite journal
  | author = Vaswani, N.|author1-link= Namrata Vaswani
 |author2=Rathi, Y. |author3=Yezzi, A. |author4=Tannenbaum, A.
  | year = 2007
  | title = Tracking deforming objects using particle filtering for geometric active contours
  | journal = IEEE Transactions on Pattern Analysis and Machine Intelligence
  | volume = 29
  | issue = 8
  | pages = 1470–1475
  | doi=10.1109/tpami.2007.1081
|pmid=17568149 |pmc=3663080 }}

==External links==
{{refbegin}}
* [http://web.maths.unsw.edu.au/~peterdel-moral/simulinks.html Feynman–Kac models and interacting particle algorithms (a.k.a. Particle Filtering)] Theoretical aspects and a list of application domains of particle filters
* [http://www-sigproc.eng.cam.ac.uk/smc/ Sequential Monte Carlo Methods (Particle Filtering)] homepage on University of Cambridge
* [https://web.archive.org/web/20060612210237/http://www.cs.washington.edu/ai/Mobile_Robotics/mcl/ Dieter Fox's MCL Animations]
* [https://web.archive.org/web/20140330053937/http://blogs.oregonstate.edu/hess/code/particles/ Rob Hess' free software]
* [http://www.jstatsoft.org/v30/i06/ SMCTC: A Template Class for Implementing SMC algorithms in C++]
* [http://www.oursland.net/projects/particlefilter/ Java applet on particle filtering]
* [https://zhouyan.github.io/vSMC/ vSMC : Vectorized Sequential Monte Carlo]
* [https://www.youtube.com/watch?v=bO_GajDgGJ4/ Particle filter explained in the context of self driving car]
{{refend}}

{{Stochastic processes}}

{{Statistics}}

{{DEFAULTSORT:Particle Filter}}
[[Category:Monte Carlo methods]]
[[Category:Computational statistics]]
[[Category:Control theory|*]]
[[Category:Nonlinear filters]]
[[Category:Robot control]]
[[Category:Statistical mechanics]]
[[Category:Sampling techniques]]
[[Category:Stochastic simulation]]