A classic problem in physics concerns normal versus anomalous diffusion. Fractal analysis of random walks with memory aims at quantitatively describing the complex phenomenology observed in economic, ecological, biological and physical systems. Markov processes exhaustively account for random walks with short-range memory. In contrast, long-range memory typically gives rise to non-Markovian walks. The most extreme case of a non-Markovian random walk corresponds to a stochastic process with dependence on the entire history of the system. We study a recently proposed non-Markovian random walk model characterized by loss of memories of the recent past and amnestically induced persistence. We report numerical and analytical results showing the complete phase diagram, consisting of 4 phases, for this system: (i) classical nonpersistence, (ii) classical persistence (iii) log-periodic nonpersistence and (iv) log-periodic persistence driven by negative feedback. The first two phases possess continuous scale invariance symmetry, however log-periodicity breaks this symmetry. Instead, log-periodic motion satisfies discrete scale invariance symmetry, with complex rather than real fractal dimensions. We find for log-periodic persistence evidence not only of statistical but also of geometric self-similarity. / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Um clássico problema em física consiste em difusão normal versus anômala. Análise fractal de caminhadas aleatórias com memória, sugere descrever quantitativamente uma fenomenologia complexa observada em economia, ecologia, biologia, e física. Processos Markovianos estão representados em caminhadas aleatórias com memória de curto alcance. Em contraste, memória de longo alcance surge tipicamente em caminhadas não-Markovianas. O caso mais extremo de uma caminhada não-Markoviana corresponde a um processo estocástico com dependência em sua história completa. Estudamos uma proposta recente de caminhada não-Markoviana caracterizada por perda de memória do passado recente e persistência induzida amnesicamente. Apresento resultados analíticos mostrando um diagrama de fase completo, consistindo de 4 fases. (i) não-persistente clássico, (ii) persistente clássico controlado por feedback positivo, (iii) não-persistente log-periódico e (iv) persistente log-periódico controlado por feedback negativo. As primeiras duas fases apresentam invariância de escala em simetria contínua. Em compensação, movimento log-periódico apresenta invariância de escala em simetria discreta, com dimensão complexa maior do que a dimensão fractal real. É mostrado evidências de persistência log-periódica não somente estatísticas, mas devido também a auto-similaridade geométrica. Obtivemos os resultados numéricos e analíticos para seis expoentes críticos, que juntos caracterizam completamente as propriedades das transições.

Darbe bus nagrinėjama mišraus tipo masinė aptarnavimo sistema, kurią gali sudaryti n paraiškų šaltinių, su atitinkamais paprasčiausių srautų intensyvumais, o paraiškos gali būti paskirstomos į m aptarnavimo įrenginių su fiksuotomis prioritetinėmis paraiškų eilėmis, kur paraiškos aptarnavimo laikas S yra pasiskirstęs pagal apibendrintą tikimybinio skirstinio funkciją G(t). Darbo tikslas – sukurti programinę įrangą, kuri pagal pateiktą sistemos funkcionavimo aprašymą schematine struktūra apskaičiuoja sistemos stacionariąsias tikimybes ir tikimybines charakteristikas. / This paper analyses the underlying multi-server and multi-class queuing system which is receiving applications of corresponding intensities distributed by Poisson process and can be spread among multi-class servers with fixed waiting positions, where service time S of a application has a general probability distribution function G(t). The object of this paper is to create the software which enables to compute stationary probabilities and to estimate stochastic characteristics of the system which is defined in schematic structure.

Nous nous intéressons aux lacets markoviens définis dans le cadre de la théorie des chaînes de Markov à temps continu sur un espace d'états discret. Ce sujet a notamment été étudié par Le Jan [LJ11] et Sznitman [Szn12]. En contraste avec ces références, nous ne supposerons pas la symétrie de la chaîne et nous intéresserons plutôt au cas infini. Tous les résultats sont présentés en termes de générateur de semi-groupe. En comparaison avec [LJ11], certaines preuves ont été détaillées ou améliorées.Nous fournissons par ailleurs quelques résultats sur les amas de boucles (voir [LJL12] dans le cas symétrique). Nous traitons notamment l'exemple du cercle discret. Nous étudions aussi les arbres couvrants définit par l'algorithme de Wilson dans le cas asymétrique.Dans la dernière partie, nous considérons la proportion des lacets couvrants l'espace. En utilisant la limite du spectre, nous donnons une expression générale de la limite de cette proportion pour une suite de graphes. Comme une application, nous donnons deux exemples concrets dans lesquels une transition de phase apparaît. / We are interested in Markov laces defined in the framework of the theory of Markov chains in continuous time on a discrete state space. This particular subject has been studied by Le Jan [LJ11] and Sznitman [Szn12]. In contrast to these references, we do not assume the reversibility of the chain and we are mostly interested in the case of countable state space. All the results are presented in terms of the generator of semigroup. In comparison with [LJ11], some demonstration has been detailed or improved.We also provide some results on the loop clusters (see [LJL12] in the reversible case). In particular, we study the example of discrete circle. We also study the spanning tree algorithm defined by Wilson in the non-symmetric case.In the last part, we consider the proportion of loops covering the whole space. Using the limit of the spectrums, we give a general expression for the limit of this ratio for a sequence of graphs. As an application, we give two examples in which a phase transition occurs.

Esse trabalho contempla o estudo sobre o estimador de mínimos quadrados obtido para sistemas lineares discretos sujeitos a ruídos aditivos e a ruídos multiplicativos em seus parâmetros. Supõe-se, adicionalmente, que os parâmetros do sistema estão sujeitos a saltos Markovianos, e que a cadeia de Markov não é conhecida. A solução do problema, sob essas hipóteses, é uma inovação apresentada nesse trabalho. Sob as mesmas hipóteses, o caso estacionário também foi contemplado, e o trabalho apresenta uma demonstração para a convergência da matriz de covariância dos erros do estimador a um valor estacionário, supondo-se estabilidade do sistema e ergodicidade da cadeia de Markov associada. Mostra-se, também, que existe uma única solução positiva semi-definida para a equação de Riccati estacionária e, ainda mais, que tal solução é o limite da matriz de covariância dos erros. A partir da introdução de uma hipótese adicional - de que os parâmetros do sistema estão sujeitos a incertezas na forma de politopos convexos - constrói-se um filtro linear dinâmico em que as iterações possuem estabilidade na média quadrática e que minimiza o limitante superior para o valor esperado do erro quadrático. Uma formulação do tipo LMI (Linear Matrix Inequalities) é proposta para a solução do problema. / This thesis deals with the linear filtering problem for discrete-time Markov jump linear systems with both additive and multiplicative noises. It is assumed that the values of the Markov chain are not available. This is the first time that a solution to the problem with these parameters is presented. By using some usual geometric arguments it is obtained a Kalman type filter conveniently implementable in a recurrence form. The stationary case is also studied and a proof for the convergence of the associated Lyapunov and Riccati like equations is presented. By adding an additional hypotesis - that the parameters of the systems are subject to convex polytopic uncertainties - it was designed a dynamic linear filter such that the closed loop system is mean square stable and minimizes an upper bound for the stationary expected value of the square error. A Linear Matrix Inequalities (LMI) formulation is proposed to solve the problem.

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.

Trata da modelagem teórica de um experimento que simula in vitro a evolução da aptidão (fitness) de uma população de virus. / We consider a nonlinear partial differential equation of conservation type to describe the dy- namics of vesicular stomatitis virus observed in aliquots of fixed particle number taken from an evolving clone at periodic intervals of time [5]. The changes in time behavior of fitness function noticed in experimental data are related to a crossover exhibited by the solutions to this equation in the transient regime for pulse-like initial conditions. As a consequence, the average replication rate of the population is predicted to reach a plateau as a power t1/ 2

In this thesis, a novel framework for dynamic congestion control has been proposed. The study is about the congestion control in broadband communication networks. Congestion results when demand temporarily exceeds capacity and leads to severe degradation of Quality of Service (QoS) and possibly loss of traffic. Since traffic is stochastic in nature, high demand may arise anywhere in a network and possibly causing congestion. There are different ways to mitigate the effects of congestion, by rerouting, by aggregation to take advantage of statistical multiplexing, and by discarding too demanding traffic, which is known as admission control. This thesis will try to accommodate as much traffic as possible, and study the effect of routing and aggregation on a rather general mix of traffic types. Software Defined Networking (SDN) and Network Function Virtualization (NFV) are concepts that allow for dynamic configuration of network resources by decoupling control from payload data and allocation of network functions to the most suitable physical node. This allows implementation of a centralised control that takes the state of the entire network into account and configures nodes dynamically to avoid congestion. Assumes that node controls can be expressed in commands supported by OpenFlow v1.3. Due to state dependencies in space and time, the network dynamics are very complex, and resort to a simulation approach. The load in the network depends on many factors, such as traffic characteristics and the traffic matrix, topology and node capacities. To be able to study the impact of control functions, some parts of the environment is fixed, such as the topology and the node capacities, and statistically average the traffic distribution in the network by randomly generated traffic matrices. The traffic consists of approximately equal intensity of smooth, bursty and long memory traffic. By designing an algorithm that route traffic and configure queue resources so that delay is minimised, this thesis chooses the delay to be the optimisation parameter because it is additive and real-time applications are delay sensitive. The optimisation being studied both with respect to total end-to-end delay and maximum end-to-end delay. The delay is used as link weights and paths are determined by Dijkstra's algorithm. Furthermore, nodes are configured to serve the traffic optimally which in turn depends on the routing. The proposed algorithm is a fixed-point system of equations that iteratively evaluates routing - aggregation - delay until an equilibrium point is found. Three strategies are compared: static node configuration where each queue is allocated 1/3 of the node resources and no aggregation, aggregation of real-time (taken as smooth and bursty) traffic onto the same queue, and dynamic aggregation based on the entropy of the traffic streams and their aggregates. The results of the simulation study show good results, with gains of 10-40% in the QoS parameters. By simulation, the positive effects of the proposed routing and aggregation strategy and the usefulness of the algorithm. The proposed algorithm constitutes the central control logic, and the resulting control actions are realisable through the SDN/NFV architecture.

The widely acknowledged performance gap between processors and memory has been the subject of much research. In the Explicitly Parallel Instruction Computing (EPIC) paradigm, the combination of in-order issue and the presence of a large number of parallel function units has further worsen the problem. Prefetching, by hardware, software or a combination of both, has been one of the primary mechanisms to alleviate this problem. In this talk, we will discuss two prefetching mechanisms, one hardware and other software, suitable for implementation in EPIC processors. Both methods rely on the off-line learning of Markovian predictors. In the hardware mechanism, the predictors are loaded into a table that is used by a prefetch engine. We have shown that the method is particularly effective for prefetching into the L2 cache. Our software mechanism which we called predicated prefetch leverages on informing loads. This is used in conjunction with data remapping and offline learning of Markovian predictors. This distinguishes our approach from early software prefetching techniques that only involves static program analysis. Our experiments show that this framework, together with the algorithms used in it, can effectively remove, in the best instance, 30% of the stall cycles due to cache misses. The results also show that the framework performs better than pure hardware stride predictors and has lower bandwidth and instruction overheads than that of pure software approaches. / Singapore-MIT Alliance (SMA)

QC 20100505

In simulation, time averages are important for estimating equilibrium parameters. In particular, we would like to have the variance, bias and mean-square error for time averages. First, we will discuss various factors and their effect on the bias, the variance and the mean-square error. We will use the Markovian Event System to model various systems, including M/M/1 queues, M/E_k/1 queues, M/M/c queues, sequential queues, inventory systems and queueing networks. We use a numerical method for the computation of the variance, the bias and the mean-square error of the time average. The effectiveness of the method is tested by experimenting with models of various stochastic systems. The contribution of this thesis is to use numerical and graphical interpretations to study the general characteristics of the measures. The important characteristics included in our study are decomposability and periodicity.