Letting Loops Loose

Monday, October 7, 2013 - 3:15pm - 4:05pm
Keller 3-180
Yuriy Mileyko (University of Hawaii at Manoa)
Problems in applied topology often require computation of an optimal (in some sense) representative among shapes satisfying particular topological constraints. In many cases this is a very challenging, if not infeasible task. Interestingly, such complex problem often can be tackled using biologically inspired algorithms. For example, slime mold can be used to construct optimal networks, ants can teach us how to find shortest paths, and simple evolutionary principles can help us find global optima. Frequently, these processes are driven by stochastic dynamics, suggesting that nature has figured out a way to efficiently sample from a distribution concentrated around the optimum. In this talk we address an example of such a phenomenon. We show that a closed polygonal chain (with large number of short links) chosen uniformly in the space of chains representing a fixed free homotopy class in a (multi-)punctured plane is, with overwhelming probability, close to the minimizing loop in this class. As a consequence, sampling from the stationary distribution of a Markov process (using, say, the Metropolis-Hastings algorithm) gives us a simple way to approximate the minimal length representative in a free homotopy class. This result finds applications in multi-agent systems, as it shows that the swarms of agents subject to obvious constraints move towards the optimal configuration without any control.
MSC Code: