How to roll a Fibonacci-sided die

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


Mark Huber (CMC)


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.

Kravis Center Lower Court 62, Claremont McKenna College

Misc. Information

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

Claremont Graduate University | Claremont McKenna | Harvey Mudd | Pitzer | Pomona | Scripps
Proudly Serving Math Community at the Claremont Colleges Since 2007
Copyright © 2018 Claremont Center for the Mathematical Sciences