Nesta tese consideramos uma nova classe de sistemas markovianos de partículas com infinitas componentes interagentes. O sistema representa a evolução temporal dos potenciais de membrana de um conjunto infinito de neurônios interagentes. Provamos a existência e unicidade do processo construindo um pseudo-algoritmo de simulação perfeita e mostrando que este algoritmo roda em um número finito de passos quase certamente. Estudamos também o comportamento do sistema quando consideramos apenas um conjunto finito de neurônios. Neste caso, construímos um procedimento de simulação perfeita para o acoplamento entre o processo limitado a um conjunto finito de neurônios e o processo que considera todos os neurônios do sistema. Como consequência encontramos um limitante superior para a probabilidade de discrepância entre os processos. / We consider a new class of interacting particle systems with a countable number of interacting components. The system represents the time evolution of the membrane potentials of an infinite set of interacting neurons. We prove the existence and uniqueness of the process, by the construction of a perfect simulation procedure. We show that this algorithm is successful, that is, we show that the number of steps of the algorithm is finite almost surely. We also study the behaviour of the system when we consider only a finite number of neurons. In this case, we construct a perfect simulation procedure for the coupling of the process with a finite number of neurons and the process with a infinite number of neurons. As a consequence we obtain an upper bound for the error we make when sampling from a finite set of neurons instead of the infinite set of neurons.

Nesta tese consideramos cadeias de alcance variável não limitado. São cadeias de alcance infinito cuja família de probabilidades de transição é representada por uma árvore de contextos probabilística. Dado uma árvore de contextos probabilística não limitada, as questões que nos interessam são as seguintes: existe ou não uma cadeia estacionária compatível com esta árvore? Se existir, esta cadeia é única? Podemos fazer uma simulação perfeita desta cadeia? Nesta tese, apresentamos novos critérios sucientes que garantem a existência e a unicidade da cadeia estacionária e, sob restrições mais fortes, a possibilidade de fazer uma simulação perfeita. Uma caraterística interessante do nosso trabalho é o fato de não utilizarmos a condição de continuidade. / We present a new perfect simulation algorithm for stationary chains (indexed by Z) having unbounded variable length memory. This is the class of innite memory chains for which the family of transition probabilities is given by probabilistic context tree. Our condition is expressed in terms of the structure of the context tree. In particular, we do not assume the continuity of the family of transition probabilities. We give an explicit construction of the chain using a sequence of i.i.d. random variables uniformly distributed in [0,1[.

Nesta tese consideramos cadeias de alcance variável não limitado. São cadeias de alcance infinito cuja família de probabilidades de transição é representada por uma árvore de contextos probabilística. Dado uma árvore de contextos probabilística não limitada, as questões que nos interessam são as seguintes: existe ou não uma cadeia estacionária compatível com esta árvore? Se existir, esta cadeia é única? Podemos fazer uma simulação perfeita desta cadeia? Nesta tese, apresentamos novos critérios sucientes que garantem a existência e a unicidade da cadeia estacionária e, sob restrições mais fortes, a possibilidade de fazer uma simulação perfeita. Uma caraterística interessante do nosso trabalho é o fato de não utilizarmos a condição de continuidade. / We present a new perfect simulation algorithm for stationary chains (indexed by Z) having unbounded variable length memory. This is the class of innite memory chains for which the family of transition probabilities is given by probabilistic context tree. Our condition is expressed in terms of the structure of the context tree. In particular, we do not assume the continuity of the family of transition probabilities. We give an explicit construction of the chain using a sequence of i.i.d. random variables uniformly distributed in [0,1[.

Perfect simulation  and the EM algorithm are the main topics in this thesis. In paper I, we present coupling from the past (CFTP) algorithms that generate perfectly distributed samples from the multi-type Widom--Rowlin-son (W--R) model and some generalizations of it. The classical W--R model is a point process in the plane or the  space consisting of points of several different types. Points of different types are not allowed to be closer than some specified distance, whereas points of the same type can be arbitrary close. A stick-model and soft-core generalizations are also considered. Further, we  generate samples without edge effects, and give a bound on sufficiently small intensities (of the points) for the algorithm to terminate. In paper II, we consider the  forestry problem on how to estimate  seedling dispersal distributions and effective plant fecundities from spatially data of adult trees  and seedlings, when the origin of the seedlings are unknown.   Traditional models for fecundities build on allometric assumptions, where the fecundity is related to some  characteristic of the adult tree (e.g.\ diameter). However, the allometric assumptions are generally too restrictive and lead to nonrealistic estimates. Therefore we present a new model, the unrestricted fecundity (UF) model, which uses no allometric assumptions. We propose an EM algorithm to estimate the unknown parameters.   Evaluations on real and simulated data indicates better performance for the UF model. In paper III, we propose  EM algorithms to  estimate the passage time distribution on a graph.Data is obtained by observing a flow only at the nodes -- what happens on the edges is unknown. Therefore the sample of passage times, i.e. the times it takes for the flow to stream between two neighbors, consists of right censored and uncensored observations where it sometimes is unknown which is which.       For discrete passage time distributions, we show that the maximum likelihood (ML) estimate is strongly consistent under certain  weak conditions. We also show that our propsed EM algorithm  converges to the ML estimate if the sample size is sufficiently large and the starting value is sufficiently close to the true parameter. In a special case we show that it always converges.  In the continuous case, we propose an EM algorithm for fitting  phase-type distributions to data.

In this thesis we study two probabilistic models defined on graphs: the Stochastic Block model and the Exponential Random Graph. Therefore, this thesis is divided in two parts. In the first part, we introduce the Krichevsky-Trofimov estimator for the number of communities in the Stochastic Block Model and prove its eventual almost sure convergence to the underlying number of communities, without assuming a known upper bound on that quantity. In the second part of this thesis we address the perfect simulation problem for the Exponential random graph model. We propose an algorithm based on the Coupling From The Past algorithm using a Glauber dynamics. This algorithm is efficient in the case of monotone models. We prove that this is the case for a subset of the parametric space. We also propose an algorithm based on the Backward and Forward algorithm that can be applied for monotone and non monotone models. We prove the existence of an upper bound for the expected running time of both algorithms. / Nessa tese estudamos dois modelos probabilísticos definidos em grafos: o modelo estocástico por blocos e o modelo de grafos exponenciais. Dessa forma, essa tese está dividida em duas partes. Na primeira parte nós propomos um estimador penalizado baseado na mistura de Krichevsky-Trofimov para o número de comunidades do modelo estocástico por blocos e provamos sua convergência quase certa sem considerar um limitante conhecido para o número de comunidades. Na segunda parte dessa tese nós abordamos o problema de simulação perfeita para o modelo de grafos aleatórios Exponenciais. Nós propomos um algoritmo de simulação perfeita baseado no algoritmo Coupling From the Past usando a dinâmica de Glauber. Esse algoritmo é eficiente apenas no caso em que o modelo é monotóno e nós provamos que esse é o caso para um subconjunto do espaço paramétrico. Nós também propomos um algoritmo de simulação perfeita baseado no algoritmo Backward and Forward que pode ser aplicado à modelos monótonos e não monótonos. Nós provamos a existência de um limitante superior para o número esperado de passos de ambos os algoritmos.

In this thesis we study two probabilistic models defined on graphs: the Stochastic Block model and the Exponential Random Graph. Therefore, this thesis is divided in two parts. In the first part, we introduce the Krichevsky-Trofimov estimator for the number of communities in the Stochastic Block Model and prove its eventual almost sure convergence to the underlying number of communities, without assuming a known upper bound on that quantity. In the second part of this thesis we address the perfect simulation problem for the Exponential random graph model. We propose an algorithm based on the Coupling From The Past algorithm using a Glauber dynamics. This algorithm is efficient in the case of monotone models. We prove that this is the case for a subset of the parametric space. We also propose an algorithm based on the Backward and Forward algorithm that can be applied for monotone and non monotone models. We prove the existence of an upper bound for the expected running time of both algorithms. / Nessa tese estudamos dois modelos probabilísticos definidos em grafos: o modelo estocástico por blocos e o modelo de grafos exponenciais. Dessa forma, essa tese está dividida em duas partes. Na primeira parte nós propomos um estimador penalizado baseado na mistura de Krichevsky-Trofimov para o número de comunidades do modelo estocástico por blocos e provamos sua convergência quase certa sem considerar um limitante conhecido para o número de comunidades. Na segunda parte dessa tese nós abordamos o problema de simulação perfeita para o modelo de grafos aleatórios Exponenciais. Nós propomos um algoritmo de simulação perfeita baseado no algoritmo Coupling From the Past usando a dinâmica de Glauber. Esse algoritmo é eficiente apenas no caso em que o modelo é monotóno e nós provamos que esse é o caso para um subconjunto do espaço paramétrico. Nós também propomos um algoritmo de simulação perfeita baseado no algoritmo Backward and Forward que pode ser aplicado à modelos monótonos e não monótonos. Nós provamos a existência de um limitante superior para o número esperado de passos de ambos os algoritmos.

Perfect simulations are methods, which convert suitable Markov chain Monte Carlo (MCMC) algorithms into algorithms which return exact draws from the target distribution, instead of approximations based on long-time convergence to equilibrium. In recent years a lot of various perfect simulation algorithms were developed. This work provides a unified exposition of some perfect simulation algorithms with applications to spatial point processes, especially to the Strauss process and area-interaction process. Described algorithms and their properties are compared theoretically and also by a simulation study.