Let Td denote the tree rooted at φ such that each vertex of Td has precisely d children. Given p ∈ (0, 1), let us assign, to each edge of Td, a label that reads trap with probability p and safe with probability 1 − p. In a bond percolation game played on Td, two players take turns to make moves, starting at the root, where a move involves relocating a token from its current position, say a vertex u of Td, to one of the children of u. A player wins if she is able to force her opponent to move the token along an edge marked a trap. We show that this game has probability 0 of resulting in a draw if and only if a related probabilistic tree automaton Bp is ergodic. We then show that Bp is non-ergodic for all p < pc and ergodic for all p ⩾ pc, where
Much of the proof involves a technique employed in showing that a given model of statistical mechanics defined on Td has a unique Gibbs measure (i.e. exhibits weak spatial mixing): establishing that no matter what boundary configuration η of states (from the alphabet associated with Bp) we assign to the vertices at generation n of Td, the effect of η, via the application of Bp, on the state of the root φ dwindles or decays as n → ∞.
Zoom link: https://icts-res-in.zoom.us/j/81366105986?pwd=Y20vNWxLemd4cVdJd1g5NHFrNWg0Zz09
Meeting ID: 813 6610 5986
This is part of the Bangalore Probability Seminar Series. For details of past and upcoming seminars kindly see Link