1. Problems
-
Problem 1.05.
[Persi Diaconis] Let $\{X_n\}_{n=0}^\infty$ be a partially exchangeable process on a graph. How long does it take to get ‘close’ to the random environment?
[for instance, see Donald Knuth Art of Computer Programming Volume 4B] -
Problem 1.1.
[Pierre Tarres] Is there a way to have more than one walk together form a partially exchangeable* process?
* - this might not be the best hypothesis.
[ref: R. Dan Mauldin] -
Consider the following signalling game. There are two players, a sender A, and a receiver B. Player A observes one of $n$ possible states of nature, and sends one of $m$ possible signals to player B, whose goal is to guess which state of nature was observed. They use the following scheme.
Initially, player A has an urn for each of the $n$ states of nature, each containing a single ball for each of the $m$ possible signals, with each ball labelled by the corresponding signal. Player B has an urn for each of the $m$ signals, each containing a ball for each of the $n$ possible states, and these balls are labelled by the states.
At each step, player A observes one of the $n$ states, chooses a random ball from their urn corresponding to that state, and sends that signal. Player B receives the signal, and chooses a random ball from their urn corresponding to that signal. This ball corresponds to one of the states, and player B guesses that state.
If the guess is correct, then there is positive reinforcement - each player duplicates the ball that they chose, adding the copy to the same urn. If the guess is incorrect, there is no change.
When $m = n = 2$, this scheme converges to perfect information transfer, with each of the two signals corresponding to one of the two states (Pemantle et al). For $m = n = 3$, there are other possible equilibria to which the scheme converges with positive probability, for instance two signals may correspond to one state, and the last to both of the other two states.Problem 1.15.
[Brian Skyrms] Modify the above scheme by adding a new ‘mutator’ ball to each of player A’s urns. When this ball is selected, player A invents a new signal and sends that. Player B responds by guessing a state uniformly at random. If this guess is correct then this new signal is added to the set of possible signals. This is done by adding one ball for this signal to each of player A’s urns, and also creating a new urn for this signal for player B, which initially contains one ball for each state. After introducing this new signal, it is reinforced once for the successful guess, duplicating one one ball each for players A and B, for the signal and state just used. If the guess is incorrect, nothing happens.
Some properties of this modified scheme are known, for instance, that the number of signals goes to infinity, but does it improve the information transfer? [Mackenzie Simper, work in progress] -
Problem 1.2.
[Yuval Peres] For a simple random walk or reversible Markov chain on a finite graph $G$, define the speedup as $$\frac{\max_u E_u(\text{Time to cover G with one walker started at $u$})}{\max_u E_u(\text{Time to cover G with $k$ walkers started at $u$})}.$$
Is this quantity bounded above by $ck$, for $c$ a constant universal over choices of graph $G$, reversible Markov chain, and $k$?
[Conjectured in 2007 by Noga Alon et al - Many Random Walks are faster than one] -
Problem 1.25.
[Christophe Sabot] Consider directed reinforced walk on $\mathbb{Z}^2$. Is this walk recurrent, starting with constant weights? -
Problem 1.3.
[Tyler Helmuth] For which sigma models (choice of target space $M$) is there an isomorphism theorem involving a self-interacting walk which is a process? Known examples are hemisphere, hyperbolic space, and Euclidean space.
A sigma model on a finite graph $G$ is $$\frac{1}{Z}\prod_{x\in V}d^M\phi e^{-\sum_{i,j\in E}f(\phi_i,\phi_j)},$$ where $d^M\phi$ is a volume measure on the manifold $M$. A good starting point is to take $M$ to be a symmetric space. -
Problem 1.35.
[Xiaolin Zeng] For a continuous-time vertex-reinforced jump process on $\mathbb{Z}^3$ with constant initial weights $\beta$, define the unique random Schroedinger operator $(-\Delta+V)$ so that $$\int_0^\infty dt E_x\mathbb{1}_{X_t=y} = \int P(dV)(-\Delta+V)^{-1}_{x,y}.$$ How does the spectrum of $(-\Delta+V)$ depend on $\beta$?
[Sabo and Zeng, 2017] -
Problem 1.4.
[Tom Spencer] For div $w$ grad on $\mathbb{Z}^d$ with $w$ uniformly elliptic i.i.d., are the eigenfunctions for energies above the ground state energy localised in $d=2$? In $d=3$, probably not. -
Problem 1.45.
[Abdelmalek Abdesselam] What can be said about the spectrum of $-\Delta^\alpha+V$ for $V$ random and $\alpha \in (0,1]$? -
Problem 1.5.
[David Brydges] Study hierarchical reinforced random walks. For instance, take an infinite grid, divided into $1 \times 1$ squares, which are grouped into nested $2 \times 2$ squares, $4 \times 4$ squares, and so on. A step consists of choosing a random nonnegative integer $k$ from some distribution, moving to a random point in the present $2^k \times 2^k square$, and reinforcing the choice of $k$.
[for instance, Drunk, Fuchs, and Zirnbauer, ’92] -
Problem 1.55.
[Sergio Bacallado] Consider a known mixture $\Pi(d\theta)$ of hierarchical walks. Given an observed walk, let $\hat\theta$ be the estimator of $\theta$. Is $\hat\theta$ consistent as we refine the hierarchy? -
Problem 1.65.
Does a spin system on another symmetric space have a random walk representation? -
Problem 1.7.
Multiplicative reinforcement as an algorithm. Is there a random walk representation?
Cite this as: AimPL: Self-interacting processes, supersymmetry, and Bayesian statistics, available at http://aimpl.org/selfsuperbayes.