Tid: 2 november 1998 kl 1515-1700

Plats : Seminarierummet 3733, Institutionen för matematik, KTH, Lindstedts väg 25, plan 7. Karta!

Föredragshållare: Prof. Mike Keane, Centrum voor Wiskunde en Informatica, Amsterdam Publikationslista (List of Publications)

Titel: Random coin tossing


In recent years probability theory has turned to the study of hidden information in various forms. This lecture deals with a simple model for hidden information with a surprising effect. Suppose that a person has two coins, one of which is fair and one of which may have a bias. The person in question produces a series of coin flips, each flip using either the fair coin or the possibly biased coin, and reports to us the sequence of heads or tails thus obtained. (S)he also divulges the manner by which she decides which coin to use, but not necessarily the coin used, at each step. We explain various manners of decision in which the biased coin will be used an infinite number of times, but in which we can never tell that it was biased, and other manners in which we can effectively determine the bias.

A precise statement of our results is:
A sequence of heads and tails is produced by repeatedly selecting a coin from two possible coins, and tossing it. The second coin is tossed at renewal times in a renewal process, and the first coin is tossed at all other times. The first coin is fair ($\text{Prob}(\text{heads}) =
1/2$), and the second coin is known either to be fair, or to have known bias $\theta\in (0,1]$($\text{Prob}(\text{heads})=\frac{1}{2}(1+\theta )$). Letting $\,u_k
:=$ Prob$\,($There is a renewal at time $\,k)$, we show that if $\sum_{k=0}^\infty u_k^2 = \infty$, we can determine, using only the sequence of heads and tails produced, if the second coin had bias $\theta$ or 0. If $\sum_{k=0}^\infty u_k^2 < 1+\frac{1}{\theta^2}$,we show that this is not possible.

This is joint work with Matthew Harris. In addition, there are recent results by Levin, Pemantle, and Perez, and also by Klaassen, showing that a phase transition can occur in the second case above and that the parameter $\theta$ can be identified. We discuss these developments and further interesting problems related to models of the above type.

Till seminarielistan
To the list of seminars