Marco Vervoort's Research

An elementary construction of an Ultrafilter on $Aleph_1$ using the Axiom of Determinateness

report ML-1994-13, ILLC Mathematical Logic (ML) series, Amsterdam, the Netherlands, 1994.

My first effort, the result of my reponse to a classroom challenge.

Abstract:

In this article we construct a free and $\sigma$-complete ultrafilter on the set $\omega_1$, using the Axiom of Determinateness (AD). First we define for each $V \subseteq \omega_1$ a perfect information game $G(V)$. The axiom AD guarantees that in each game $G(V)$, either the first or the second player has a winning strategy. For several different constructions of $V$ from other sets, we construct winning strategies in the game $G(V)$. We show that these constructions correspond to closure properties of the set $\{V \mid \mbox{player I has a winning strategy in $G(V)$}\}$. Finally we show that this set is a free and $\sigma$-complete ultrafilter on $\omega_1$.

Blackwell Games

1. my 'afstudeerscriptie' (near equivalent to Master's Thesis).
2. in: Statistics, probability and Game Theory. Papers in Honor of David Blackwell', IMS Lecture Notes - Monograph Series 30, T.S. Ferguson, L.S. Shapley and J.B. MacQueen (editors), 1996.

I did this research this for my 'afstudeerscriptie', and then rewrote it as an article.

Abstract:

Blackwell games are infinite games of imperfect information. The two players simultaneously make their moves and are then informed of each other's moves. Payoff is determined by a Borel measurable function $f$ on the set of possible resulting sequences of moves. A standard result in Game Theory is that finite games of this type are determined. Blackwell proved that infinite games are determined, but only for the cases where the payoff function is the indicator function of an open or $G_\delta$ set. For games of perfect information, determinacy has been proven for games of arbitrary Borel complexity. In this paper I prove the determinacy of Blackwell games over a $G_{\delta\sigma}$ set, in a manner similar to Davis' proof of determinacy of games of $G_{\delta\sigma}$ complexity of perfect information.

There is also extensive literature about the consequences of assuming AD, the axiom that {\em all} such games of perfect information are determined \cite{AD-1,AD-2}. In the final section of this paper I formulate an analogous axiom for games of imperfect information, and explore some of the consequences of this axiom.

The Strength of Blackwell Determinacy

with Donald .A. Martin, Itay Neeman. To appear.

Prof. D.A. Martin, inspired by my work on Blackwell games, proceeded to find a proof of determinacy of Blackwell games for all levels of the Borel hierarchy. This is a later article, in which he and Itay Neeman shows that Blackwell determinacy implied perfect information determinacy (as well as the other way around). I contributed part of the proof of one of the core lemmas (during email discussions), and hence am listed as co-author of the paper.

Reinforced Random Walks

To appear. Still undergoing rewriting

A rewrite of part of my thesis. The original used non-standard analysis, but this was considered to make the article too inaccessible.

Abstract:

This article is about recurrence in reinforced random walks, where edges in a graph are traversed with probabilities that may be different (reinforced) at second, third etc. traversals. After a brief review of general theory, we focus on the case where the probability for any edge only changes once, after its first traversal. As a special case, we show that the once-reinforced random walk on the infinite ladder is almost surely recurrent if reinforcement is small, extending a result by Thomas Sellke from an at this time unpublished article\cite{sellke}. Then we adapt these techniques to show that for a class of graphs which generalizes the infinite ladder, recurrence also holds for sufficiently \emph{large} reinforcements.

Towards High Speed Grammar Induction on Large Text Corpora

With Pieter W. Adriaans, Marten Trautwein. In: SOFSEM 2000: Theory and Practice of Informatics, Lecture Notes in Computer Science 1963, V. Hlavác, K.G. Jeffery and J. Wiedermann (editors), 2000.

As part of my PhD research, I wrote the Emile program: using concepts from Pieter Adriaans, this program reads in a text, and without prior knowledge attempts to determine the grammatical structure of the language. This article reviews the basic concepts and algorithms of the program, as well as the results of this approach, both in theory and in practice.

Games, Walks and Grammars: Problem's I've Worked On

PhD Dissertation. Appeared as nr. DS-2000-03 in the ILLC Dissertation (DS) Series.

This thesis is one-third Blackwell Games, one-third Random Walks, and one-third Emile Grammar Parser, with no connection between the three parts. As the triple abstract is rather lenghty, it is not included on this page.