When

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

End : 11/09/2016 - 5: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.