Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, March 02, 2017, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Pascal Pfister

Asymptotically Optimal Amplifiers for the Moran Process

We study the Moran process, a model of an evolving population with two kinds of individuals — “mutants” and “non-mutants”. The individuals reside at the vertices of a graph G – each vertex contains exactly one individual, and it is either a mutant or a non-mutant. In the initial state, one vertex (chosen uniformly at random) contains a mutant. All of the other vertices contain non-mutants. Additionally, mutants have fitness r > 1 whereas non-mutants have fitness 1. At each time step, a vertex v is selected at random, with probability proportional to its fitness. Next, a neighbour w of v is selected uniformly at random and the state of vertex v (mutant or non-mutant) is copied to vertex w. If G is finite and connected then with probability 1, the process will either reach the state where there are only mutants (known as fixation) or it will reach the state where there are only non-mutants (extinction).
A family of graphs is said to be strongly amplifying if the extinction probability (the probability that there are no mutants left at some point) tends to 0 when the Moran process is run on graphs in this family. We show that there is an infinite family of undirected graphs, called dense incubators, whose extinction probability is O(n^−1/3). We show that this is optimal, up to constant factors. Moreover, we introduce sparse incubators, for varying edge density, and show that the extinction probability of these graphs is O(n/m), where m is the number of edges. Again, we show that this is optimal, up to constant factors.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login