Learning models on rooted regular trees with majority update policy: convergence and phase transition
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917672096104448 |
|---|---|
| author | Podder, Moumanti Sarkar, Anish |
| author_facet | Podder, Moumanti Sarkar, Anish |
| contents | We study a learning model in which an agent is stationed at each vertex of $\mathbb{T}_{m}$, the rooted tree in which each vertex has $m$ children. At any time-step $t \in \mathbb{N}_{0}$, they are allowed to select one of two available technologies: $B$ and $R$. Let the technology chosen by the agent at vertex $v\in\mathbb{T}_{m}$, at time-step $t$, be $C_{t}(v)$. Let $\{C_{0}(v):v\in\mathbb{T}_{m}\}$ be i.i.d., where $C_{0}(v)=B$ with probability $π_{0}$. During epoch $t$, the agent at $v$ performs an experiment that results in success with probability $p_{B}$ if $C_{t}(v)=B$, and with probability $p_{R}$ if $C_{t}(v)=R$. If the children of $v$ are $v_{1},\ldots,v_{m}$, the agent at $v$ updates their technology to $C_{t+1}(v)=B$ if the number of successes among all $v_{i}$ with $C_{t}(v_{i})=B$ exceeds, strictly, the number of successes among all $v_{j}$ with $C_{t}(v_{j})=R$. If these numbers are equal, then the agent at $v$ sets $C_{t+1}(v)=B$ with probability $1/2$. Else, $C_{t+1}(v)=R$. We show that $\{C_{t}(v):v\in\mathbb{T}_{m}\}$ is i.i.d., where $C_{t}(v)=B$ with probability $π_{t}$, and $\{π_{t}\}_{t \in \mathbb{N}_{0}}$ converges to a fixed point $π$ of a function $g_{m}$. For $m \geqslant 3$, there exists a $p(m) \in (0,1)$ such that $g_{m}$ has a unique fixed point, $1/2$, when $p \leqslant p(m)$, and three distinct fixed points, of the form $α$, $1/2$ and $1-α$, when $p > p(m)$. When $m=3$, $p_{B}=1$ and $p_{R} \in [0,1)$, we show that $g_{3}$ has a unique fixed point, $1$, when $p_{R} < \sqrt{3}-1$, two distinct fixed points, one of which is $1$, when $p_{R} = \sqrt{3}-1$, and three distinct fixed points, one of which is $1$, when $p_{R} > \sqrt{3}-1$. When $g_{m}$ has multiple fixed points, we also specify which of these fixed points $π$ equals, depending on $π_{0}$. For $m=2$, we describe the behaviour of $g_{3}$ for all $p_{B}$ and $p_{R}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_12418 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Learning models on rooted regular trees with majority update policy: convergence and phase transition Podder, Moumanti Sarkar, Anish Probability We study a learning model in which an agent is stationed at each vertex of $\mathbb{T}_{m}$, the rooted tree in which each vertex has $m$ children. At any time-step $t \in \mathbb{N}_{0}$, they are allowed to select one of two available technologies: $B$ and $R$. Let the technology chosen by the agent at vertex $v\in\mathbb{T}_{m}$, at time-step $t$, be $C_{t}(v)$. Let $\{C_{0}(v):v\in\mathbb{T}_{m}\}$ be i.i.d., where $C_{0}(v)=B$ with probability $π_{0}$. During epoch $t$, the agent at $v$ performs an experiment that results in success with probability $p_{B}$ if $C_{t}(v)=B$, and with probability $p_{R}$ if $C_{t}(v)=R$. If the children of $v$ are $v_{1},\ldots,v_{m}$, the agent at $v$ updates their technology to $C_{t+1}(v)=B$ if the number of successes among all $v_{i}$ with $C_{t}(v_{i})=B$ exceeds, strictly, the number of successes among all $v_{j}$ with $C_{t}(v_{j})=R$. If these numbers are equal, then the agent at $v$ sets $C_{t+1}(v)=B$ with probability $1/2$. Else, $C_{t+1}(v)=R$. We show that $\{C_{t}(v):v\in\mathbb{T}_{m}\}$ is i.i.d., where $C_{t}(v)=B$ with probability $π_{t}$, and $\{π_{t}\}_{t \in \mathbb{N}_{0}}$ converges to a fixed point $π$ of a function $g_{m}$. For $m \geqslant 3$, there exists a $p(m) \in (0,1)$ such that $g_{m}$ has a unique fixed point, $1/2$, when $p \leqslant p(m)$, and three distinct fixed points, of the form $α$, $1/2$ and $1-α$, when $p > p(m)$. When $m=3$, $p_{B}=1$ and $p_{R} \in [0,1)$, we show that $g_{3}$ has a unique fixed point, $1$, when $p_{R} < \sqrt{3}-1$, two distinct fixed points, one of which is $1$, when $p_{R} = \sqrt{3}-1$, and three distinct fixed points, one of which is $1$, when $p_{R} > \sqrt{3}-1$. When $g_{m}$ has multiple fixed points, we also specify which of these fixed points $π$ equals, depending on $π_{0}$. For $m=2$, we describe the behaviour of $g_{3}$ for all $p_{B}$ and $p_{R}$. |
| title | Learning models on rooted regular trees with majority update policy: convergence and phase transition |
| topic | Probability |
| url | https://arxiv.org/abs/2405.12418 |