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
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
This treatise is on simple random walk, and on the way it gives rise to Brownian motion. It was written as my bachelor project, and it was written in such a way that it should serve as a good...Show moreThis treatise is on simple random walk, and on the way it gives rise to Brownian motion. It was written as my bachelor project, and it was written in such a way that it should serve as a good introduction into the subject for students that have as much knowledge as I when I began working on it. That is: a basic probability course, and a little bit of measure theory. To that end, the following track is followed: In section 1, the simple random walk is defined. In section 2, the first major limit property is studied: whether the walk be recurrent or not. Some calculus and the discrete Fourier transform are required to prove the result. In section 3, a second limit property is studied: its range, or, the number of visited sites. In the full proof of the results, the notion of strong and weak convergence presents itself, and also the notion of tail events. To understand these problems more precisely, and as a necessary preparation for Brownian motion, some measure theoretic foundations are treated in section 4. Emphasis is put, not on the formal derivation of the results, but on the right notion of them in our context. In section 5, Brownian motion is studied. First, in what manner simple random walk gives rise to it, and secondly its formal definition. Special care is devoted to explain the exact steps that are needed for its construction, for that is something which I found rather difficult to understand from the texts I read on it.Show less
This thesis divides naturally into two chapters. In the first chapter, the concept of division algebra is defined as a (not necessarily associative) algebra in which left- and right-multiplication...Show moreThis thesis divides naturally into two chapters. In the first chapter, the concept of division algebra is defined as a (not necessarily associative) algebra in which left- and right-multiplication with a non-zero element is bijective. It is noted that the zero algebra, the Real numbers and the Complex numbers form division algebras of respective dimension 0, 1 and 2 over R. In the rest of the chapter, it is proven that furthermore, the Hamilton numbers (otherwise known as the Quaternions) form a 4-dimensional division algebra over R, and that the Cayley numbers (otherwise known as the Octonions) form an 8-dimensional division algebra over R. The first chapter is based on [Baez 2001] and it assumes basic familiarity with linear algebra. It is known that the five algebras mentioned above are in fact the only five finite-dimensional division algebras over R. A proof of this is far beyond the scope of this thesis, but in the second chapter at least it is shown that there exist no division algebras over R of odd dimension greater than 1. To achieve this we prove that the existence of division algebras of dimension n over R implies the parallelisability of the n − 1-sphere, a definition of which is provided at the beginning of that chapter. To prove that for even n the n-sphere is not parallelisable we make use in section 2.3 of the Brouwer degree. Before the Brouwer degree can even be defined however we have to establish reduced singular homology in section 2.2, which actually takes up the largest part of chapter 2. The general idea and proofs of many of the lemmata and propositions of Chapter 2 have been adapted from [Hatcher 2002]. The second chapter assumes basic familiarity with topology, category theory and homological algebra. For a good introduction to both category theory and homological algebra, see [Doray 2007].Show less
Deze scriptie gaat over de statistische berekeningen die gebruikt zijn voor de rechtszaak van Lucia de B. Zij is in juni 2004 door het gerechtshof in Den Haag veroordeeld voor 7 moorden en 3...Show moreDeze scriptie gaat over de statistische berekeningen die gebruikt zijn voor de rechtszaak van Lucia de B. Zij is in juni 2004 door het gerechtshof in Den Haag veroordeeld voor 7 moorden en 3 pogingen tot moord. Zij heeft hiervoor levenslang en TBS gekregen. Zij heeft in verschillende ziekenhuizen gewerkt waaronder het Juliana Kinderziekenhuis (JKZ) en het Rode Kruis Ziekenhuis (RKZ). De statisticus dr. Elffers is door de rechter gevraagd om een statistisch rapport te schrijven over de zaak. In eerste instantie heeft hij alleen berekeningen gedaan voor het JKZ, omdat alleen van dat ziekenhuis de gegevens vrij gegeven waren. In dit ziekenhuis zijn ze haar gaan verdenken, omdat er erg veel incidenten tijdens haar diensten plaats vonden (onder incidenten worden sterfgevallen en reanimaties verstaan). Op verzoek van de rechter zijn later ook berekeningen gedaan voor twee afdelingen van het RKZ waar ze in dezelfde periode gewerkt heeft. Men vroeg zich af of het toeval zou kunnen zijn dat Lucia betrokken was bij al die incidenten, terwijl ze onschuldig was. De rechter heeft tijdens de rechtszaak aan dr. Elffers gevraagd wat de kans is dat het toeval zou kunnen zijn dat Lucia bij zoveel incidenten aanwezig was. Dr. Elffers heeft uitgerekend wat de kans is dat een willekeurig persoon betrokken kan zijn bij zoveel incidenten, als de incidenten volgens toeval gebeuren. Waarom zijn deze berekeningen zo belangrijk en welke invoeld hebben ze tijdens de rechtszaak gehad? Statistici geloofden dat er medisch bewijs was voor de moorden en de medici geloofden dat daar statistisch bewijs voor was. Dit heeft er toe geleid dat de rechter Lucia schuldig heeft bevonden. In deze scriptie zullen we kijken naar de berekeningen die dr. Elffers gedaan heeft, de aanmerkingen daarop en mogelijke verbeteringen. Hiervoor worden alternatieve statistische toetsingsgrootheden besproken en met elkaar vergeleken.Show less
Gaussische kromming is een eigenschap gedefinieerd op tweedimensionale differentieerbare vari¨eteiten. Voor bepaalde numerieke berekeningen kan het nodig zijn om met triangulaties van zulke...Show moreGaussische kromming is een eigenschap gedefinieerd op tweedimensionale differentieerbare vari¨eteiten. Voor bepaalde numerieke berekeningen kan het nodig zijn om met triangulaties van zulke oppervlakken te werken in plaats van met een analytische beschrijving. In dit verslag zal ik ingaan op het schatten van Gaussische kromming op punten van zo’n getrianguleerd oppervlak. Ik zal een methode beschrijven gebaseerd op de stelling van Gauss-Bonnet, en laten zien hoe deze zich in de praktijk gedraagt aan de hand van een aantal triangulaties.Show less
