How to roll a Fibonacci-sided die

When
Start: 11/09/2016 - 4:15pm
End  : 11/09/2016 - 5:15pm

Category
Colloquium

Speaker
Mark Huber (CMC)

Abstract

The Fibonacci numbers come from a famous recursive sequence: $F_n = F_{n-1} + F_{n-2}$. They also count the number of {\em isolated sequences} of length $n$, where an isolated sequence is a sequence of 0's and 1's where no two 1's are adjacent. For instance, 0101 and 1000 are isolated, while 0110 is not. In this talk, I'll present a method for drawing uniformly from the set of isolated sequences of length $n$ using linear expected time. The algorithm also gives a way of extending the probability distribution on finite sequences out to infinite sequences. Along the way we'll use this algorithm to prove some asymptotic facts about the Fibonacci numbers, and derive the exact solution. This method is wide ranging, and can be used for arbitrary order $k$ recursive sequences with positive coefficients.

Where
Kravis Center Lower Court 62, Claremont McKenna College

Misc. Information

 This talk is a replacement of the previously scheduled talk by Mark Alber.