Spelling suggestions: "subject:"[een] MARKOV CHAINS"" "subject:"[enn] MARKOV CHAINS""
101 |
Privacy preservation in internet of things : a game theory based approach / Protection de la vie privée dans internet des objets : une approche basée théorie des jeuxRiahi Sfar, Arbia 16 November 2017 (has links)
La question de sécurité a toujours constitué un défi pour les chercheurs dans le domaine des réseaux de communication. L’apparition de nouveaux paradigmes, applications et des technologies d’un côté ; l’ubiquité et l’hétérogénéité des entités communicantes d’un autre côté, ont induit des problèmes de sécurité très complexes. Les préjudices engendrés sur la vie privée des utilisateurs peuvent être irréparables. D’abord, nous avons proposé une approche systémique et cognitive permettant d’inclure les aspects de sécurité d’Internet des Objets (IdO) dans un cadre cohérent. Comparé à l’approche analytique, elle peut manquer de rigueur théorique, mais reste flexible et utilisable dans la prise de décision dans l’environnement ubiquitaire d’IdO. Ensuite, nous avons défini des questions liées aux menaces accidentelles ou intentionnelles, pouvant arriver en cas de compromission de données privées échangées. La caractérisation du problème a eu lieu en étudiant les concepts fondamentaux dans IdO et les travaux de recherche effectués dans le contexte de la sécurité. En examinant les différents travaux de recherche, nous avons constaté que plusieurs solutions classiques restent applicables de point de vue sécurité mais sont limitées par des contraintes d’énergie, de mémoire et de capacité de calcul. Pour y remédier, nous avons visé à construire une réponse pragmatique en utilisant la théorie des jeux. L’avantage de cette approche réside dans ses bases mathématiques et formelles solides permettant d’atteindre les meilleurs équilibres. Après, nous avons justifié analytiquement nos choix portant sur des éléments essentiels de notre système, leurs interactions et leurs objectifs. Nous avons utilisé un calcul probabiliste basé sur un processus Markovien. Dans notre approche, nous avons défini trois scénarios différents (e-santé, commerce et transport intelligent), deux acteurs principaux (DH : Data Holder, et DR : Data Requester), ayant des comportements de types différents (trusted-regular, trusted-curious, untrusted-curious et untrusted-malicious), et un ensemble de stratégies dépendant de quatre paramètres (moyens de communication, détection d’attaque, motivation financière, et concession sur les données privées). Enfin, nous avons montré l’existence d’un équilibre du jeu avec une valeur de motivation financière et un niveau de protection des données privées satisfaisants, et en calculant les probabilités correspondantes. Nous avons validé notre modèle en obtenant des résultats numériques conformes à ceux tirés du modèle théorique. / Security questions have always constituted a research challenge in the field of communication networks. The appearance of new paradigms, concepts, applications and technologies from one hand, and the ubiquity and the heterogeneity of the communicating entities from another hand, led to new complex problems of security. In some cases, the damages caused to the private life of every user can be irreparable. First, we propose a systemic and cognitive approach to include all Internet of Things (henceforth IoT) security aspects in a coherent framework. Compared to the analytic approach, our vision may lack theoretical rigor, but remains a flexible approach that may be required during decision making in ubiquitous environment. Next, we identify precise questions related to accidental or intentional threats, which may lead to private data breach during their exchange over networks. Then, we characterize the privacy problem by studying the fundamental concepts of IoT and the research activities related to security. By examining the related research work, it has been noticed that several classical solutions remain applicable but are limited by energy constraints, memory space, and calculation capacities. To overcome this problem, we propose a logical and controllable solution based on game theory approach. The advantage of this choice resides in its solid mathematical and formal basis. Then, we analytically explain the choice of the main system components, their interactions and their objectives. We used a probabilistic approach using a Markovian process, where we define three different application scenarios (e-health, trade and intelligent transport), two main actors (private data owner and requester) with different player’s types (trusted-regular, trusted-curious, untrusted-curious and untrusted-malicious), and a set of strategies depending on communication facilities, attack detection, incentive motivation and privacy concession. Finally, we evaluate the model by demonstrating the existence of an equilibrium solution with a satisfactory value of incentive motivation and data privacy concession, and by calculating the final state probabilities. We validate the proposed model through numerical results obtained from the theoretical model.
|
102 |
Ruleta a herní systémy / Roulette and its strategiesZadražil, Tomáš January 2017 (has links)
Objective of this thesis is to describe history of gambling, in a context of roulette to explain basic and advanced parts of probability theory which allow to the reader to decide about function of several popular roulette systems. There was mainly used expected value of discrete random variable, homogenous discrete-time Markov chain and simulations made in programming language R. Concrete output of the thesis are in precisely calculated expected values of a profit with fixed spins and with chosen limitation and corresponding estimations provided by simulation. On the basis of that it's possible to decide which systems are functional and which are not. Main contribution of this text is in didactical approach which helps to describe popular problematics of roulette systems by using basic and advanced areas of probability theory.
|
103 |
Improved Usage Model for Web Application Reliability TestingWan, Bo January 2012 (has links)
Testing the reliability of an application usually requires a good usage model that accurately captures the likely sequences of inputs that the application will receive from the environment. The models being used in the literature are mostly based on Markov chains. They are used to generate test cases that are statistically close to what the applica-tion is expected to receive when in production. In this thesis, we propose a model for reli-ability testing that is created directly from the log file of a web application. Our proposed model is also based on Markov chains and has two components: one component, based on a modified tree, captures the most frequent behaviors, while the other component is another Markov chain that captures infrequent behaviors. The result is a statistically cor-rect model that shows clearly what most users do on the site.
The thesis also presents an evaluation method for estimating the accuracy of vari-ous reliability-testing usage models. The method is based on comparison between ob-served users’ traces and traces inferred from the usage model. Our method gauges the accuracy of the reliability-testing usage model by calculating the sum of goodness-of-fit values of each traces and scaling the result between 0 and 1. Finally, we present an experimental study on the log of a real web site and discuss the way to use proposed usage model to generate test sequences, as well as strength and weakness of the model for reliability testing.
|
104 |
Optimalizace růstu populace řas pomocí Markovských procesů a simulačních technik / Optimization of Algae Population Growth Using Markov Chains andZouharová, Martina January 2010 (has links)
The thesis deals with the task of refining the constructional and operational parameters of a tubular photobioreactor in order to maximise the growth rate of algae contained in the cultivation suspension. It builds on a basic growth model of the Porhydrium sp. alga, and focuses on the optimization of external irradiance, which is one of the key determinants of algae growth. Two distinct methodological approaches are applied: analytic approach, which employs Markov Chains, and simulation approach, which relies on agent-based simulations. In the analytic part, we introduce the construction of state transition matrix for a Markov Chain that accounts for varying irradiance inside the photobioreactor (in contrast to constant-irradiance methods that have been published so far). In the simulation part, we devised an agent-based model of algae population that enables us to analyze the system behaviour while interactively changing the model parameters. In the context of the results from both the analytic and simulation part, we conclude by suggesting the optimal level of external irradiance.
|
105 |
Teoremas limiares para o modelo SIR estocástico de epidemia / Threshold theorems for the SIR stochastic epidemic modelEstrada López, Mario Andrés, 1989- 27 August 2018 (has links)
Orientador: Élcio Lebensztayn / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-27T01:18:53Z (GMT). No. of bitstreams: 1
EstradaLopez_MarioAndres_M.pdf: 691310 bytes, checksum: c03e392b197051a7368585d6c09a7835 (MD5)
Previous issue date: 2015 / Resumo: Este trabalho tem como objetivo estudar o modelo SIR (suscetível-infectado-removido) de epidemia nas versões determinística e estocástica. Nosso objetivo é encontrar limitantes para a probabilidade de que o tamanho da epidemia não sobrepasse certa proporção do número inicial de suscetíveis. Iniciamos apresentando as definições e a dinâmica do processo de epidemia determinístico. Obtemos um valor limiar para o número inicial de suscetíveis para que a epidemia exploda ou não. Consideramos o modelo de epidemia estocástico SIR assumindo que não há período latente, isto é, que um infectado pode transmitir a infecção ao instante de ser contagiado. O modelo é considerado com uma configuração inicial de suscetíveis e infectados e é feita especial ênfases no estudo da variável aleatória ''tamanho da epidemia'', que é definida como a diferença entre o número de suscetíveis ao começar e ao terminar a propagação da doença. Como na parte determinística, obtemos teoremas limiares para o modelo de epidemia estocástico. Os métodos usados para encontrar os limitantes são os de análise da cadeia de Markov imersa e de comparação estocástica / Abstract: This work has as objective to study the SIR (susceptible-infected-removed) epidemic model in the deterministic and stochastic version. Our objective is to find bounds for the probability that the size of the epidemic does not exceed certain proportion of the initial number of susceptible individuals. We begin presenting the definitions and the dynamics for the deterministic model for a general epidemic. We obtain a threshold value for the initial number of susceptible individuals for the epidemic to build up or not. As fundamental part of this work, we consider a stochastic epidemic SIR model assuming there is no latent period, that is, one infected can transmit the infection at the moment of being infected. The model is considered with an initial configuration of susceptible and infected individuals and the study is focused on the random variable ''size of the epidemic'', which is defined as the difference between the number of susceptible individuals at the start and at the end of the propagation of the epidemic. As in the deterministic part, we obtain a threshold theorem for the stochastic epidemic. The methods used to prove the theorem are analysis of the embedded chain and the stochastic comparison / Mestrado / Estatistica / Mestre em Estatística
|
106 |
Modelagem de contextos para aprendizado automático aplicado à análise morfossintática / Modeling contexts for automatic learning applied to morphosyntactic analysisFábio Natanael Kepler 28 May 2010 (has links)
A etiquetagem morfossintática envolve atribuir às palavras de uma sentença suas classes morfossintáticas de acordo com os contextos em que elas aparecem. Cadeias de Markov de Tamanho Variável (VLMCs, do inglês \"Variable-Length Markov Chains\") oferecem uma forma de modelar contextos maiores que trigramas sem sofrer demais com a esparsidade de dados e a complexidade do espaço de estados. Mesmo assim, duas palavras do português apresentam um alto grau de ambiguidade: \'que\' e \'a\'. O número de erros na etiquetagem dessas palavras corresponde a um quarto do total de erros cometidos por um etiquetador baseado em VLMCs. Além disso, essas palavras parecem apresentar dois diferentes tipos de ambiguidade: um dependendo de contexto não local e outro de contexto direito. Exploramos maneiras de expandir o modelo baseado em VLMCs através do uso de diferentes modelos e métodos, a fim de atacar esses problemas. As abordagens mostraram variado grau de sucesso, com um método em particular (aprendizado guiado) se mostrando capaz de resolver boa parte da ambiguidade de \'a\'. Discutimos razões para isso acontecer. Com relação a \'que\', ao longo desta tese propusemos e testamos diversos métodos de aprendizado de informação contextual para tentar desambiguá-lo. Mostramos como, em todos eles, o nível de ambiguidade de \'que\' permanece praticamente constante. / Part-of-speech tagging involves assigning to words in a sentence their part-of-speech class based on the contexts they appear in. Variable-Length Markov Chains (VLMCs) offer a way of modeling contexts longer than trigrams without suffering too much from data sparsity and state space complexity. Even so, two words in Portuguese show a high degree of ambiguity: \'que\' and \'a\'. The number of errors tagging these words corresponds to a quarter of the total errors made by a VLMC-based tagger. Moreover, these words seem to show two different types of ambiguity: one depending on non-local context and one on right context. We searched ways of expanding the VLMC-based model with a number of different models and methods in order to tackle these issues. The approaches showed variable degrees of success, with one particular method (Guided Learning) solving much of the ambiguity of \'a\'. We explore reasons why this happened. Rega rding \'que\', throughout this thesis we propose and test various methods for learning contextual information in order to try to disambiguate it. We show how, in all of them, the level of ambiguity shown by \'que\' remains practically c onstant.
|
107 |
Autour de quelques chaines de Markov combinatoires / Some results concerning Markov chains on combinatorials objectsNunzi, Francois 12 December 2016 (has links)
On s'intéresse à deux classes de chaînes de Markov combinatoires. On commence avec les chaînes de Markov de Jonglage, inspirées du modèle de jonglage introduit par Warrington, pour lesquelles on définit des généralisations multivariées des modèles existants. On en calcule les mesures stationnaires et les facteurs de normalisation que l'on exprime par des formules explicites. On s'intéresse également au cas limite où la hauteur maximale à laquelle le jongleur peut lancer ses balles tend vers l'infini. On propose alors une reformulation de la chaîne de Markov en termes de partitions d'entiers, ce qui permet aussi de définir un modèle où le jongleur manipule une infinité de balles. Les preuves sont obtenues en utilisant une chaîne enrichie sur les partitions d'ensembles. On exhibe également, pour l'un des modèles, une propriété de convergence ultrarapide : la mesure stationnaire y est atteinte en un nombre fini d'étapes. Dans le Chapitre suivant, on s'intéresse à des généralisations multivariées de ces modèles : on considère cette fois un jongleur manipulant des balles de différents poids, et lorsqu'une balle entre en collision avec une balle plus légère, cette dernière est éjectée vers le haut, pouvant à son tour en heurter une autre plus légère, jusqu'à ce qu'une balle atteigne l'emplacement le plus élevé. On donnera ici encore une formule explicite pour les mesures stationnaires et les facteurs de normalisation. Dans le dernier Chapitre, on s'intéresse cette fois au modèle du tas de sable stochastique, pour lequel on démontre une conjecture posée par Selig, selon laquelle la mesure stationnaire ne dépend pas de la loi d'ajout des grains de sable. / We consider two types of combinatoric Markov chains. We start with Juggling Markov chains, inspired from Warrington's model. We define multivariate generalizations of the existing models, for which we give stationary mesures and normalization factors with closed-form expressions. We also investigate the case where the maximum height at which the juggler may send balls tends to infinity. We then reformulate the Markov chain in terms of integer partitions, which allows us to consider the case where the juggler interacts with infinitely many balls. Our proofs are obtained through an enriched Markov chain on set partitions. We also show that one of the models has the ultrafast convergence property : the stationary mesure is reached after a finite number of steps. In the following Chapter, we consider multivariate generalizations of those models : the juggler now juggles with balls of different weights, and when a heavy ball collides with a lighter one, this light ball is bumped to a higher position, where it might collide with a lighter one, until a ball reaches the highest position. We give closed-form expressions for the stationary mesures and the normalization factors. The last Chapter is dedicated to the stochastic sandpile model, for which we give a proof for a conjecture set by Selig : the stationary mesure does not depend on the law governing sand grains additions.
|
108 |
Dynamic network formation / Dynamique de formation des réseauxVarloot, Rémi 01 June 2018 (has links)
Cette thèse porte sur la rapidité du temps de mélange de chaînes de Markov sur des graphes. La contribution principale concerne les graphes avec des dynamiques locales sur les arêtes, la topologie du graphe évoluant au fur et à mesure que les arêtes glissent les unes le long des autres. Nous proposons une classification des différents modèles existants de graphes dynamiques, tout en illustrant l’importance des transitions le long d’une structure mouvante pour améliorer la vitesse de convergence. Cette étude est complétée par la preuve, pour l’une de ces dynamiques, d’un temps de mélange rapide. Nous définissons notamment l’expansion partielle d’un graphe. Celle-ci permet de suivre l’avancement de la dynamique, partant d’un état de faible expansion, jusqu’à obtention d’une bonne expansion à l’équilibre. La fin de cette thèse porte sur une amélioration de l’algorithme de simulation parfaite de Propp et Wilson. Nous introduisant un oracle pour les transitions, inspiré de l’échantillonnage préférentiel, qui permet de réduire la complexité de l’algorithme. Nous fournissons une preuve de correction, ainsi qu’une étude de l’impact de cette méthode sur la vitesse d’échantillonnage d’ensembles indépendants pour certains graphes. / This thesis focuses on the rapid mixing of graph-related Markov chains. The main contribution concerns graphs with local edge dynamics, in which the topology of a graph evolves as edges slide along one another. We propose a classification of existing models of dynamic graphs, and illustrate how evolving along a changing structure improves the convergence rate. This is complemented by a proof of the rapid mixing time for one such dynamic. As part of this proof, we introduce the partial expansion of a graph. This notion allows us to track the progression of the dynamic, from a state with poor expansion to good expansion at equilibrium. The end of the thesis proposes an improvement of the Propp and Wilson perfect sampling technique. We introduce oracle sampling, a method inspired by importance sampling that reduces the overall complexity of the Propp and Wilson algorithm. We provide a proof of correctness, and study the performance of this method when sampling independent sets from certain graphs.
|
109 |
Multilevel Approximations of Markovian Jump Processes with Applications in Communication NetworksVilanova, Pedro 04 May 2015 (has links)
This thesis focuses on the development and analysis of efficient simulation and inference techniques for Markovian pure jump processes with a view towards applications in dense communication networks. These techniques are especially relevant for modeling networks of smart devices —tiny, abundant microprocessors with integrated sensors and wireless communication abilities— that form highly complex and diverse communication networks. During 2010, the number of devices connected to the Internet exceeded the number of people on Earth: over 12.5 billion devices. By 2015, Cisco’s Internet Business Solutions Group predicts that this number will exceed 25 billion.
The first part of this work proposes novel numerical methods to estimate, in an efficient and accurate way, observables from realizations of Markovian jump processes. In particular, hybrid Monte Carlo type methods are developed that combine the exact and approximate simulation algorithms to exploit their respective advantages. These methods are tailored to keep a global computational error below a prescribed global error tolerance and within a given statistical confidence level. Indeed, the computational work of these methods is similar to the one of an exact method, but with a smaller constant. Finally, the methods are extended to systems with a disparity of time scales.
The second part develops novel inference methods to estimate the parameters of
Markovian pure jump process. First, an indirect inference approach is presented, which is based on upscaled representations and does not require sampling. This method is simpler than dealing directly with the likelihood of the process, which, in general, cannot be expressed in closed form and whose maximization requires computationally intensive sampling techniques. Second, a forward-reverse Monte Carlo Expectation-Maximization algorithm is provided to approximate a local maximum or saddle point of the likelihood function of the parameters given a set of observations.
The third part is devoted to applications in communication networks where also mean field or fluid approximations techniques, to substantially reduce the computational work of simulating large communication networks are explored. These methods aim to capture the global behaviour of systems with large state spaces by using an aggregate approximation, which is often described by means of a non-linear dynamical system.
|
110 |
Modeling IP traffic using the batch Markovian arrival processKlemm, Alexander, Lindemann, Christoph, Lohmann, Marco 10 December 2018 (has links)
In this paper, we show how to utilize the expectation-maximization (EM) algorithm for efficient and numerical stable parameter estimation of the batch Markovian arrival process (BMAP). In fact, effective computational formulas for the E-step of the EM algorithm are presented, which utilize the well-known randomization technique and a stable calculation of Poisson jump probabilities. Moreover, we identify the BMAP as an analytically tractable model of choice for aggregated traffic modeling of IP networks. The key idea of this aggregated traffic model lies in customizing the BMAP such that different lengths of IP packets are represented by rewards of the BMAP. Using measured traffic data, a comparative study with the MMPP and the Poisson process illustrates the effectiveness of the customized BMAP for IP traffic modeling by visual inspection of sample paths over several time scales, by presenting important statistical properties as well as by investigations of queuing behavior.
|
Page generated in 0.0564 seconds