We study discounted random walks in directed graphs. In each step, the walk either terminates with a constant probability $α$, or proceeds to a random out-neighbor. Our goal is to estimate the probability $π(s, t)$ that a discounted random walk starting from $s$ terminates at $t$. This probability is also known as the Personalized PageRank (PPR) score, which measures the relevance of $t$ to $s$, for instance, when $s$ and $t$ are web pages on the Internet. We aim to estimate $π(s, t)$ within a constant relative error with constant probability. A variety of algorithms have been developed for several problem variants, such as single-pair, single-source, single-target, and single-node estimation, under both worst-case and average-case settings, and for different combinations of allowed graph queries. However, in many important cases, there remain polynomial gaps between known upper and lower bounds. In this paper, we establish tight bounds for all problem variants and query combinations, closing all existing gaps in both the worst-case and average-case settings. We provide tight (up to logarithmic factors) lower bounds, showing that for all but one query combination, existing algorithms are already optimal. For the remaining case, we design a novel algorithm that matches our new lower bound, thereby achieving optimality. This is the first algorithm to exploit this specific query combination. It uses a new randomized bidirectional framework that combines randomized backward propagation with selective Monte Carlo estimation.

翻译：我们研究有向图中的折扣随机游走。在每一步中，游走以恒定概率 $α$ 终止，或以等概率转移到随机出邻居节点。我们的目标是估计从起点 $s$ 出发的折扣随机游走终止于节点 $t$ 的概率 $π(s, t)$。该概率亦称为个性化PageRank（PPR）分数，用于衡量 $t$ 对 $s$ 的相关性，例如当 $s$ 和 $t$ 为互联网上的网页时。我们旨在以恒定概率实现恒定相对误差范围内对 $π(s, t)$ 的估计。针对多种问题变体（如单点对、单源、单目标及单节点估计），已在最坏情况与平均情况设定下，针对不同允许的图查询组合开发了多种算法。然而，在许多重要情形中，已知上界与下界之间仍存在多项式级差距。本文中，我们为所有问题变体及查询组合建立了紧致界，填补了最坏情况与平均情况设定下的所有现有空白。我们给出了紧致（至对数因子）的下界，表明除一种查询组合外，现有算法均已达到最优。针对剩余情形，我们设计了一种匹配新下界的新颖算法，从而实现了最优性。这是首个利用该特定查询组合的算法，其采用了一种结合随机反向传播与选择性蒙特卡洛估计的新型随机双向框架。