In 1993 Häggström [3] derived a characterisation of the uniform spanning tree on the {0, 1}×Z lattice, or shorthand 2-lattice. He proposed a way to extend to the {0, ...m − 1} × Z lattice, or...Show moreIn 1993 Häggström [3] derived a characterisation of the uniform spanning tree on the {0, 1}×Z lattice, or shorthand 2-lattice. He proposed a way to extend to the {0, ...m − 1} × Z lattice, or shorthand m-lattice. We propose a characterisation for the m-lattice that is slightly more compact, but the main ideas are the same. We use a different representation of spanning trees, or rather it is a representation for so called special forests, namely a sequence of letters and partitions. A special forest may be viewed as a spanning tree in the making. We have found a characterisation of the uniform spanning tree on the m-lattice. The results may be extended to so called repetitive graphs. Others have used the same representation of special forests to find a recurrence relation for the number of spanning trees and of Hamilton cycles of various (finite) repetitive graphs. Finally we discuss the matrix tree theorem and the Markov chain tree theorem. Combining these two theorems immediately proves a formula for the stationary distribution of an irreducible, aperiodic Markov chain.Show less
If 𝑚 denotes the number of digits in the regular continued fraction expansion that can be determined from 𝑛 digits in the decimal expansion, then Lochs’ Theorem states that the fraction 𝑚 𝑛...Show moreIf 𝑚 denotes the number of digits in the regular continued fraction expansion that can be determined from 𝑛 digits in the decimal expansion, then Lochs’ Theorem states that the fraction 𝑚 𝑛 converges Lebesgue almost surely to a fraction of two entropies as 𝑛 → ∞. These are the entropies of the interval maps that generate these expansions. Lochs’ Theorem has been generalized to pairs of interval maps that both belong to a class of piecewise monotonic transformations that generate expansions and that admit an invariant density with suitable ergodic properties. The first aim of this thesis is to review sufficient conditions on interval maps to belong to this class. For this, we first of all recover the famous existence result for invariant densities by Lasota and Yorke for expanding piecewise monotonic interval maps. As an example of a nonexpanding piecewise monotonic interval map, we also consider the Liverani-Saussol-Vaienti (LSV) map and provide a new proof of the already known result that such a map admits an invariant probability density if and only the corresponding parameter lies in (0, 1). Motivated by the practical use of beta encoders, one of the main goals in this thesis is to extend Lochs’ Theorem to expansions generated by a class of random piecewise monotonic interval maps. We review sufficient conditions on random interval maps to belong to this class. For two random interval maps 𝑇 and 𝑆 in this class, we show that, if 𝑚 denotes the number of digits in the 𝑆-expansion that can be determined from 𝑛 digits in the 𝑇-expansion, then, roughly speaking, the fraction 𝑚 𝑛 converges Lebesgue almost surely to a fraction of two fiber entropies as 𝑛 → ∞. As a second important goal, we prove that the skew product of an LSV map with parameter in (0, 1) and another LSV map with parameter in [1, ∞) and with underlying Bernoulli shift admits an invariant probability density.Show less
Hidden Models arise if an unobserved process is partially observed through a noisy channel. Such an model is referred to as a Hidden Markov Model if the unobserved process is assumed to be a Markov...Show moreHidden Models arise if an unobserved process is partially observed through a noisy channel. Such an model is referred to as a Hidden Markov Model if the unobserved process is assumed to be a Markov process. Often true statistical properties of unobserved processes are unknown. Hence, for this general Hidden Model we are seeking an universal method for decoding the observed noisy sequences. The problem is solved by the Discrete Universal Denoiser (DUDE) for discrete-valued observed data. The key assumption in the DUDE is, that the combined hidden and observed process is stationary. The case of continuous observed data is dealt with by quantizing the outputs and applying an extended version of the DUDE. We show an improvement for the DUDE and an optimization strategy for the continuous data.Show less
In this bachelor thesis we study plagiarism detection in computer programs using various information-theoretic and probabilistic concepts. We aim to make the detection methods as general as...Show moreIn this bachelor thesis we study plagiarism detection in computer programs using various information-theoretic and probabilistic concepts. We aim to make the detection methods as general as possible by basing them on a minimum amount of domain knowledge. Ideally this would allow us to develop a method in one domain, and then easily apply it in many other domains with minimal adjustments. In Chapter 2 we introduce the problem of plagiarism in computer source code. In Chapter 3 we give a short overview of prior research in this field. Then in Chapter 4 we describe a new method for plagiarism detection, which we apply in Chapter 6 to two data sets of source code submitted by first year university students for an introductory programming course. We find that the method is able to successfully detect various types of plagiarism. The use of statistical methods to flag suspected regions and calculate p-values is the most important novel part of this thesis. To prepare for Chapter 5, we describe some information theoretic concepts in detail in the Appendix. We introduce the Kullback-Leibler divergence (also called relative entropy), and prove some of its most important properties. Then, after introducing another concept called relative entropy rates, which generalize the concept of relative entropy from random variables to random processes, we apply this to our data sets in Chapter 6, giving us a way to compare the students who wrote the source code in a data set, and calculate how similar they are. This thesis was written for a double bachelors degree in Mathematics and Computer Science at Leiden University, under supervision of E. Verbitskiy for the Mathematical Institute, and W. Kosters for the Leiden Institute for Advanced Computer Science.Show less
The oxidation of CO on the Pd(100)(√ 5 × √ 5)R27◦ surface is studied using the kinetic Monte Carlo simulation method. The occupation by oxygen of a specific type of site – the hollow sites – is...Show moreThe oxidation of CO on the Pd(100)(√ 5 × √ 5)R27◦ surface is studied using the kinetic Monte Carlo simulation method. The occupation by oxygen of a specific type of site – the hollow sites – is monitored in order to gain insight into experiments on the restructuring of the surface which itself might be a explanation of oscillations measured in the reactivity in the oxidation reaction. Two indications have been found that oxygen atoms will only vacate the hollow sites that are they normally occupy in a clean oxidized surface if their place is taken by CO molecules.Show less
The oxidation of CO on the Pd(100)(√ 5 × √ 5)R27◦ surface is studied using the kinetic Monte Carlo simulation method. The occupation by oxygen of a specific type of site – the hollow sites – is...Show moreThe oxidation of CO on the Pd(100)(√ 5 × √ 5)R27◦ surface is studied using the kinetic Monte Carlo simulation method. The occupation by oxygen of a specific type of site – the hollow sites – is monitored in order to gain insight into experiments on the restructuring of the surface which itself might be a explanation of oscillations measured in the reactivity in the oxidation reaction. Two indications have been found that oxygen atoms will only vacate the hollow sites that are they normally occupy in a clean oxidized surface if their place is taken by CO molecules.Show less
We have analyzed a model proposed by Steil et al. [1] for glucose metabolism. The model consists of 5 differential equations describing the change of a patient’s blood glucose concentration to his...Show moreWe have analyzed a model proposed by Steil et al. [1] for glucose metabolism. The model consists of 5 differential equations describing the change of a patient’s blood glucose concentration to his/her basal and bolus insulin pump data. This relatively simple model of 8 parameters was analyzed using measured plasma insulin and blood glucose concentrations from a study by the Amsterdam Medical Centre of 10 patients of the span of approximately 43 hours. In this study almost continuous blood insulin measurements were taken, in addition to insulin pump data and blood glucose measurements. This is quite difficult to measure, so this gave us a unique opportunity to individually analyze sections of the model. We have obtained relatively good fits for the insulin plasma submodel on most patients. Our optimisation remained inconclusive on the remaining blood glucose submodel, and alternative formulations to solve this also gave insufficient results. In conclusion, the linear submodel for insulin plasma concentrationsl described the data, while the remaining submodel for glucose and alternative formulations of it are still in need of further study.Show less
