Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 288 - Probability and Statistics

Van Vu

UCSD

On an urn model of Diaconis

Abstract:

We consider the following urn model proposed by Diaconis. There is an urn with $n$ balls, each ball has value 0 or 1. Pick two random balls and add a new ball with their sum (modulo 2) to the urn. (Thus the number of balls increases by one each time). What is the limiting distribution? In general, let $G$ be a finite additive group. We begin with an $a$ set $g_1, \dots, g_n$ of (not necessarily different) elements of $G$. (In fact, typically $n$ is much larger than $|G|$). At time $i=0,1,2,\dots,$ we choose two random elements $a$ and $b$ from the set $g_1, \dots, g_{n+i}$ and add the sum $g_{n+i+1} = a+b$ to the set. Siegmund and Yakir studied the distribution of the set $g_1,g_2\dots$ and showed that it converges to the uniform distribution. This result leaves open the question: How quickly does this convergence occur? In this talk we address this issue.

Host:

October 28, 2004

10:00 AM

AP&M 6438

****************************