Stochastic matrix | EPFL Graph Search

In mathematics, a stochastic matrix is a square matrix used to describe the transitions of a Markov chain. Each of its entries is a nonnegative real number representing a probability. It is also called a probability matrix, transition matrix, substitution matrix, or Markov matrix. The stochastic matrix was first developed by Andrey Markov at the beginning of the 20th century, and has found use throughout a wide variety of scientific fields, including probability theory, statistics, mathematical finance and linear algebra, as well as computer science and population genetics. There are several different definitions and types of stochastic matrices: :A right stochastic matrix is a real square matrix, with each row summing to 1. :A left stochastic matrix is a real square matrix, with each column summing to 1. :A doubly stochastic matrix is a square matrix of nonnegative real numbers with each row and column summing to 1

Modeling an America's Cup Regatta as a Sequential Stochastic Game

Jean-Benoît Rossel

The main objective of this thesis is to model a regatta in the America’s Cup, and more precisely the first leg of the race, where the two competing sailboats have to move upwind. During the race, each crew attempts to be the first to reach the end of this leg, and is allowed to hinder its opponent as long as certain rules are respected. A boat which finishes this leg first is often able to manage its lead until the end of the regatta. An essential ingredient of the problem is the study of different maneuvers that the boats can execute during the race, as well as the effect generated by the presence of a boat on the wind around it. Indeed, a boat located just behind its opponent will receive less wind in its sails, and its speed will consequently be reduced. The boats considered in our model are of the type Class America, which were in used in the America’s Cup between 1982 and 2007. The race can hence be viewed as a game between two players which are assumed to be identical, in which each of them can make decisions sequentially. The goal of each player is to finish the first upwind leg with the largest lead possible over the opponent. The boats progress in an environment in which the wind fluctuates unpredictably. Thus, the game is a sequential stochastic game, in which each player will try to determine a sequence of actions which is the most favorable on average. A mathematical study of this kind of game will be done, and a strategy will be built by using tools of dynamic programming. A theorem will prove that this strategy is optimal, in the sense that no player has interest to deviate from this strategy. The last part of this thesis consists of applying the mathematical study of sequential stochastic games in the context of a sailing regatta. Given the current positions of the boats as well as the current state of the wind, a set of available actions and reactions for the boats can be defined. Each choice will bring the boats up to some new positions, where a new decision process will begin in a new state of the wind. Once the rules of the game are established, the objective is to define an algorithm which allows to build a strategy which will be an approximation of the optimal strategy. The implementation of this algorithm could produce a tool for decision support, that the crew could use on board during the regatta.

EPFL2013

Forward-Backward Splitting for Optimal Transport Based Problems

Mireille El Gheche, Pascal Frossard, Guillermo Ortiz Jimenez, Hermina Petric Maretic, Effrosyni Simou

Optimal transport aims to estimate a transportation plan that minimizes a displacement cost. This is realized by optimizing the scalar product between the sought plan and the given cost, over the space of doubly stochastic matrices. When the entropy regularization is added to the problem, the transportation plan can be efficiently computed with the Sinkhorn algorithm. Thanks to this breakthrough, optimal transport has been progressively extended to machine learning and statistical inference by introducing additional application-specific terms in the problem formulation. It is however challenging to design efficient optimization algorithms for optimal transport based extensions. To overcome this limitation, we devise a general forward-backward splitting algorithm based on Bregman distances for solving a wide range of optimization problems involving a differentiable function with Lipschitz-continuous gradient and a doubly stochastic constraint. We illustrate the efficiency of our approach in the context of continuous domain adaptation. Experiments show that the proposed method leads to a significant improvement in terms of speed and performance with respect to the state of the art for domain adaptation on a continually rotating distribution coming from the standard two moon dataset.

2020

Weighted Gossip: Distributed Averaging Using Non-Doubly Stochastic Matrices

Florence Bénézit, Patrick Thiran, Martin Vetterli

This paper presents a general class of gossip-based averaging algorithms, which are inspired from Uniform Gossip [1]. While Uniform Gossip works synchronously on complete graphs, weighted gossip algorithms allow asynchronous rounds and converge on any connected, directed or undirected graph. Unlike most previous gossip algorithms [2]–[6], Weighted Gossip admits stochastic update matrices which need not be doubly stochastic. Double-stochasticity being very restrictive in a distributed setting [7], this novel degree of freedom is essential and it opens the perspective of designing a large number of new gossip-based algorithms. To give an example, we present one of these algorithms, which we call One-Way Averaging. It is based on random geographic routing, just like Path Averaging [5], except that routes are one way instead of round trip. Hence in this example, getting rid of double stochasticity allows us to add robustness to Path Averaging.

IEEE2010

Modeling an America's Cup Regatta as a Sequential Stochastic Game

Jean-Benoît Rossel

EPFL2013