ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG satisfy the paper's general-graph regularity assumption, and let Vnn≥1\\{V_n\\}_{n \ge 1} satisfy the candidate-set assumption. For each initial source vv, write Pv\mathbb{P}_v for probability under source vv, let v∗v^* be the true source, let v^B(t)\widehat{v}_B(t) be the estimator at time tt, let π(t)\pi(t) be the observation history up to time tt, let dd be graph distance, and let FvF_v denote the relevant graph-dependent time-scaling function. General-graph estimation-error conjecture. There are constants a1”=a1”(G,Q0,Q1)a_1”=a_1”(G,Q_0,Q_1) and b1”=b1”(G)b_1”=b_1”(G) such that

lim⁡n→∞max⁡v∈VnPv(min⁡0≤t≤Fv(a1”log⁡n)Eπ(t)[d(v∗,v^B(t))]≤b1”⋅Eπ(0)[d(v∗,v^B(0))])=0.\lim_{n\to\infty}\max_{v\in V_n}\mathbb{P}_v\left(\min_{0\le t\le F_v(a_1”\log n)}\mathbb{E}_{\pi(t)}[d(v^*,\widehat{v}_B(t))]\le b_1”\cdot\mathbb{E}_{\pi(0)}[d(v^*,\widehat{v}_B(0))]\right)=0.

The claim is presented as an expected extension of the paper's lower-bound lemma from regular trees and lattices to suitable general graphs; the displayed text leaves the referenced graph and candidate-set assumptions unspecified, so its precise scope and eventual status require verification.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.