In this thesis I’ll discuss Conditional Independencies of Joint Probability Distributions (here after called CI’s respectively JPD’s) over a finite set of discrete random variables. Remember that...Show moreIn this thesis I’ll discuss Conditional Independencies of Joint Probability Distributions (here after called CI’s respectively JPD’s) over a finite set of discrete random variables. Remember that for any such JPD we can write down a list of all CI’s, between two subsets of variables given a third. Such a list is called a CI-trace. An arbitrary list of CI’s is called a CI-pattern, without a priori knowing if there will exist a corresponding JPD with this CI-pattern. For simplicity and without loss of generality we take all JPD’s over n + 1 variables and label them by the integers 0, 1, . . . , n. A CI-trace now becomes a set of triples consisting of subsets of [n], the random variables (with [n] I denote the set {0, 1, . . . , n}). For example (A, B, C) with A, B and C ⊂ [n] is such a triple, it can also be denoted as A⊥B|C, which means that the random variables of A are independent of the random variables of B given any outcome on the random variables of C. It was believed that CI-traces could be characterised by some finite set of rules, called Conditional Independence rules, CI-rule. Such a CI-rule would state that if a CI-trace contains a certain pattern of triplets it should also contain a certain other triple. Furthermore such a pattern of a CI-rule should itself be finite; it should consist of k CI’s, called the antecedents that would validate another k + 1’th CI, called the consequent. The order of a CI-rule is the number k of its antecedents. This idea would imply that the set of all CI-traces is equal to the set of all CI-patterns closed under the CI-rules. In 1992 Milan Studen´y wrote an article on this subject called Conditional Independence Relations have no finite complete characterisation. He proved that such a characterisation is not possible. Now the main goal of my thesis was to understand this article and to work out a readable version of the theorem and the proof. The proof is based on two major parts. First of all the existence of a particular JPD and its CI-pattern on n + 1 variables and secondly on a proposition about CI-patterns based on entropies. The remainder of my thesis will contain sections on these two major parts, Studen´y’s theorem and a small summary of the changes I made.Show less
This Bachelor’s thesis is about the complexity of the multichain classification problem. The problem is to detect whether a given Markov decision process is unichain or multichain. A Markov...Show moreThis Bachelor’s thesis is about the complexity of the multichain classification problem. The problem is to detect whether a given Markov decision process is unichain or multichain. A Markov decision process is unichain if the corresponding Markov chain contains only one recurrent class (and a possibly empty set of transient states) for every strategy, otherwise it is multichain. We first show that the general case is NP-complete. A polynomial algorithm is given for Markov decision processes that contain either a state which is recurrent for all strategies or a state which is absorbing under some strategy. The deterministic case is considered to be polynomial, but we only give an outline of the algorithm. We will provide a complete polynomial algorithm to reduce the problem for deterministic Markov decision processes. At last we will discuss some other polynomial algorithms, including an algorithm that reduces the multichain classification problem for a general Markov decision process in polynomial time to a multichain classification problem for a communicating Markov decision process (for every pair of states i, j there is a strategy such that i is reachable from j in the corresponding Markov chain).Show less
Het ladenprincipe, ook wel bekend onder de naam duivenhokprincipe, zegt in zijn simpelste vorm dat als een voldoende aantal objecten verdeeld wordt over niet te veel laden, er minstens ´e´en lade...Show moreHet ladenprincipe, ook wel bekend onder de naam duivenhokprincipe, zegt in zijn simpelste vorm dat als een voldoende aantal objecten verdeeld wordt over niet te veel laden, er minstens ´e´en lade is die veel van deze objecten bevat. In 1930 ontdekte Frank P. Ramsey [Ramsey] een bijzondere uitbreiding van dit principe die onder andere zegt dat als we de verzameling van takken van een oneindige volledige graaf in twee klassen verdelen, er een oneindige volledige deelgraaf is waarvan alle takken tot dezelfde klasse behoren. Het principe toont aan dat vanaf een bepaalde omvang willekeurige structuren noodzakelijkerwijs regelmatige deelstructuren moeten bevatten. Dit verslag geeft de resultaten van het onderzoek dat gedaan is naar de Stelling van Ramsey en de mogelijke uitbreidingen hiervan. Veel resultaten komen tot stand door het nemen van een partitie van een verzameling en vervolgens op een handige manier de verschillende objecten van de verzameling in de juiste klassen van de partitie te plaatsen. We spreken vanwege deze reden vaak over partitierelaties en noemen de stellingen die we behandelen partitiestellingen. Hoofdstuk 1 is een inleiding in partitierelaties en vormt de basis voor alles wat verder volgt. Het hoofdstuk is met name belangrijk omdat het partitiesymbool hierin ge¨ıntroduceerd wordt. Door gebruik te maken van dit symbool kunnen partitierelaties op een korte en duidelijke manier weergegeven worden. Hoofdstuk 2 behandelt de Stelling van Ramsey en geeft een beperkte uitbreiding van deze stelling. De Stelling van Erd˝os en Rado wordt in hoofdstuk 3 behandeld. Deze stelling is een uitbreiding van de stelling van Ramsey naar het overaftelbare geval. Het hoofdstuk kan het beste gelezen worden na hoofdstuk 2 aangezien het een logisch vervolg hierop is. Er wordt aangenomen dat de lezer bekend is met de basisprincipes van de verzamelingenleer. Een korte herhaling van de belangrijkste begrippen en notatie, wordt gegeven in de bijlage. Een andere belangrijke aanname die we maken is het keuzeaxioma; dat wil zeggen, we gebruiken het axiomastelsel van Zermelo–Fraenkel altijd samen met het keuzeaxioma. De belangrijkste bron waar gebruik van is gemaakt tijdens het onderzoek, is [Erd˝os et al.]. Voor een ieder die meer wil weten over het onderwerp is dit boek aan te raden.Show less
Beschrijvende verzamelingenleer is de studie van definieerbare deelverzamelingen van R. We zijn ge¨ınteresseerd in hoe goed deze verzamelingen zich gedragen. Vragen die wij proberen te beantwoorden...Show moreBeschrijvende verzamelingenleer is de studie van definieerbare deelverzamelingen van R. We zijn ge¨ınteresseerd in hoe goed deze verzamelingen zich gedragen. Vragen die wij proberen te beantwoorden zijn onder anderen: welke deelverzamelingen van R voldoen aan de continuumhypothese (dat wil zeggen, hebben aftelbare ¨ cardinaliteit of de cardinaliteit van het continuum), en welke deelverzamelingen zijn ¨ (Lebesgue)meetbaar. We proberen zo groot mogelijke klassen te maken die een positief antwoord geven op voorgaande vragen door te beginnen met eenvoudig te beschrijven verzamelingen, zoals de open en gesloten verzamelingen, en vervolgens nieuwe verzamelingen te cre¨eren door middel van simpele operaties zoals aftelbare verenigingen, complementen en continue beelden. We ordenen de zo verkregen verzamelingen de complexiteit van hun beschrijving. In deze inleiding in de beschrijvende verzamelingenleer introduceren we een aantal belangrijke begrippen uit het vakgebied, namelijk de Poolse ruimten, in het bijzonder 2N en N N, de Borelverzamelingen en de analytische verzamelingen, en geven een aantal fundamentele eigenschappen van deze begrippen. In hoofdstuk 1 behandelen we de Poolse ruimten. Dit zijn de topologische ruimten die van groot belang blijken te zijn voor de studie van R. In hoofdstuk 2 beschouwen we de Borelhi¨erarchie. In deze hi¨erarchie bouwen we de klasse der Borelverzamelingen van onder op door te beginnen met de open verzamelingen, vervolgens complementen toe te voegen, daarvan alle aftelbare verenigingen toe te voegen, van die verzamelingen weer de complementen erbij doen en zo verder. Herhaling van dit proces geeft uiteindelijk alle Borelverzamelingen in R. In hoofdstuk 3 bekijken we de analytische verzamelingen. Dit zijn projecties van Borelverzamelingen. Het blijkt dat elke Borelverzameling analytisch is, maar er is (in R) een analytische verzameling die niet Borel is. We zullen dit bewijzen, en ook bewijzen dat elke analytische verzameling Lebesguemeetbaar is.Show less
In the 40s, Mac Lane and Eilenberg introduced categories. Although by some referred to as abstract nonsense, the idea of categories allows one to talk about mathematical objects and their...Show moreIn the 40s, Mac Lane and Eilenberg introduced categories. Although by some referred to as abstract nonsense, the idea of categories allows one to talk about mathematical objects and their relationions in a general setting. Its origins lie in the field of algebraic topology, one of the topics that will be explored in this thesis. First, a concise introduction to categories will be given. Then, a few examples of categories will be presented. After this, two specific categories will be singled out and treated in more detail, namely the category of π-sets and the category of covering spaces for space X (with certain conditions) with π the fundamental group of X. The main theorem that will be proved is that these two categories are “equivalent”. This means that we can translate problems from one category, in this case the category of covering spaces, to problems in the category of G-sets. In certain instances this proves to be fruitful as certain problems are more easily solved algebraically than topologically. As an application, a slightly weaker form of the famous Seifert-van Kampen theorem will be proved using the equivalence of categories.Show less
We show how the theory of multiplier ideals can be developed and discuss several applications of this theory. In the second section the same theory in the analytic setting is developed and several...Show moreWe show how the theory of multiplier ideals can be developed and discuss several applications of this theory. In the second section the same theory in the analytic setting is developed and several applications are given. Let X be a smooth algebraic variety and D an effective Q-divisor. We associate to D (or to the pair (X, D)) an ideal sheaf I(D) which controls the behavior of the fractional part of D and determines how close it is to have an simple normal crossing support. Other applications can be treated such as singularities of projective hypersurfaces and characterization of divisors. In the former case a result of Esnault-Viehweg concerning the least degree of hypersurfaces with multiplicity greater than or equal to a given positive integer at each point of a finite set is explained and proved in two different ways. A slight generalization is also given. Several vanishing and non-vanishing results including a global generation theorem are treated which will be used to prove the results about singularities. In the second section the analytic analogues of the materials in section one are given and the characterization of analytic nef and good divisors are explained.Show less
In this Bachelor Thesis, we will explain a calculus named Schubert Calculus. Schubert Calculus is invented by Hermann C¨asar Hannibal Schubert around the end of the nineteenth century. This...Show moreIn this Bachelor Thesis, we will explain a calculus named Schubert Calculus. Schubert Calculus is invented by Hermann C¨asar Hannibal Schubert around the end of the nineteenth century. This calculus allowed Schubert and his successors to solve many enumerative problems in geometry, although they didn’t have rigorous proofs of the rules in this calculus. This is the reason why Hilbert’s 15-th problem concerns with this calculus, and nowadays most of the rules in this calculus are finally formalized (through topology and intersection theory). The main purpose of this Bachelor Thesis is to explain the rules of this Schubert Calculus and solve some enumerative problems. The first chapter introduces the Grassmann Variety (mainly from [KL]), and the second chapter gives some basic facts about the cohomology ring of this Grassmann Variety (mainly based on [KL], [FU] and [ST]). In the third and the fifth chapter we will develop the calculus in this cohomology ring (mainly from [KL] and [ST]). The fourth chapter shows the power of the Schubert Calculus by solving several enumerative problems (many of which are new). I have decided not to include complete proofs of the formulae from the second chapter, since the complete proofs I know are very technical (although we will give a sketch). Proofs can be found, for example, in [GH] (although it contains some errors), [FU] (as exercises) and [HP] (but this is hard to read). For more details and proofs of Chapter Five, I suggest to read [FU]. I have also decided not to include (part of) the theory of Schubert Polynomials and Varieties, which is a current area of research, since a detailed introduction can be found in [FU].Show less
