Tue, 17 Jun 2008
14:00 -
18:00
Gibson 1st Floor SR
Mon, 09 Jun 2008
12:00 -
13:00
Gibson 1st Floor SR
Tue, 27 May 2008
12:00 -
13:00
Gibson 1st Floor SR
OxMOS Team Meeting
Duvan Henao and Xianmin Xu
(Oxford)
Abstract
Duvan will be talking on "Cavitation, invertibility, and the continuity of the determinant in critical cases", and Xianmin willl be talking about his work on numerical simulations of cavitation in nonlinear elasticity
Fri, 23 May 2008
15:15 -
16:15
L3
The real field with an irrational power function and a dense multiplicative subgroup
Philipp Heironymi
(Oxford)
Tue, 13 May 2008
14:30
14:30
L3
Killed Branching Random Walks
Louigi Addario-Berry
(Oxford)
Abstract
Joint work with Nicolas Broutin.
The problem is related to searching in trees. Suppose we are given a complete binary tree (a rooted tree in which the root has degree 2 and every other vertex has degree 3) with independent, identically distributed random edge weights (say copies of some random variable X, which need not be non-negative). The depth d(v) of a vertex v is the number of edges on the path from v to the root. We give each vertex v the label S_v which is the sum of the edge weights on the path from v to the root. For positive integers n, we let M_n be the maximum label of any vertex at depth n, and let M^* = max {M_n: n =0,1,...}. It is of course possible that M^* is infinity.
Under suitable moment assumptions on X, it is known that there is a constant A such that M_n/n --> A almost surely and in expectation. We call the cases A>0, A=0, and A< 0 supercritical, critical, and subcritical, respectively. When A <= 0 it makes sense to try to find the vertex of maximum weight M* in the whole tree. One possible strategy is to only explore the subtree T_0 containing the root consisting only of vertices of non-negative weight. With probability bounded away from zero this strategy finds the vertex of maximum weight. We derive precise information about the expected running time for this strategy. Equivalently, we derive precise information about the random variable |T_0|. In the process, we also derive rather precise information about M*. This answers a question of David Aldous.
The problem is related to searching in trees. Suppose we are given a complete binary tree (a rooted tree in which the root has degree 2 and every other vertex has degree 3) with independent, identically distributed random edge weights (say copies of some random variable X, which need not be non-negative). The depth d(v) of a vertex v is the number of edges on the path from v to the root. We give each vertex v the label S_v which is the sum of the edge weights on the path from v to the root. For positive integers n, we let M_n be the maximum label of any vertex at depth n, and let M^* = max {M_n: n =0,1,...}. It is of course possible that M^* is infinity.
Under suitable moment assumptions on X, it is known that there is a constant A such that M_n/n --> A almost surely and in expectation. We call the cases A>0, A=0, and A< 0 supercritical, critical, and subcritical, respectively. When A <= 0 it makes sense to try to find the vertex of maximum weight M* in the whole tree. One possible strategy is to only explore the subtree T_0 containing the root consisting only of vertices of non-negative weight. With probability bounded away from zero this strategy finds the vertex of maximum weight. We derive precise information about the expected running time for this strategy. Equivalently, we derive precise information about the random variable |T_0|. In the process, we also derive rather precise information about M*. This answers a question of David Aldous.