More Like this

1. Fraud Detection for Random Walks

   https://doi.org/10.4230/LIPIcs.ITCS.2024.36  

   Dani, Varsha; Hayes, Thomas P; Pettie, Seth; Saia, Jared (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Guruswami, Venkatesan (Ed.)

   Traditional fraud detection is often based on finding statistical anomalies in data sets and transaction histories. A sophisticated fraudster, aware of the exact kinds of tests being deployed, might be difficult or impossible to catch. We are interested in paradigms for fraud detection that are provably robust against any adversary, no matter how sophisticated. In other words, the detection strategy should rely on signals in the data that are inherent in the goals the adversary is trying to achieve. Specifically, we consider a fraud detection game centered on a random walk on a graph. We assume this random walk is implemented by having a player at each vertex, who can be honest or not. In particular, when the random walk reaches a vertex owned by an honest player, it proceeds to a uniformly random neighbor at the next timestep. However, when the random walk reaches a dishonest player, it instead proceeds to an arbitrary neighbor chosen by an omniscient Adversary. The game is played between the Adversary and a Referee who sees the trajectory of the random walk. At any point during the random walk, if the Referee determines that a {specific} vertex is controlled by a dishonest player, the Referee accuses that player, and therefore wins the game. The Referee is allowed to make the occasional incorrect accusation, but must follow a policy that makes such mistakes with small probability of error. The goal of the adversary is to make the cover time large, ideally infinite, i.e., the walk should never reach at least one vertex. We consider the following basic question: how much can the omniscient Adversary delay the cover time without getting caught? Our main result is a tight upper bound on this delay factor. We also discuss possible applications of our results to settings such as Rotor Walks, Leader Election, and Sybil Defense. 

   more » « less
2. COVER TIME FOR THE FROG MODEL ON TREES

   https://doi.org/10.1017/fms.2019.37  

   HOFFMAN, CHRISTOPHER; JOHNSON, TOBIAS; JUNGE, MATTHEW (January 2019, Forum of Mathematics, Sigma)

   The frog model is a branching random walk on a graph in which particles branch only at unvisited sites. Consider an initial particle density of $$\unicode[STIX]{x1D707}$$ on the full $$d$$ -ary tree of height $$n$$ . If $$\unicode[STIX]{x1D707}=\unicode[STIX]{x1D6FA}(d^{2})$$ , all of the vertices are visited in time $$\unicode[STIX]{x1D6E9}(n\log n)$$ with high probability. Conversely, if $$\unicode[STIX]{x1D707}=O(d)$$ the cover time is $$\exp (\unicode[STIX]{x1D6E9}(\sqrt{n}))$$ with high probability. 

   more » « less
3. On the cover time of dense graphs

   Frieze, Alan; Pegden, W.; Tkocz, T. (January 2019, SIAM journal on discrete mathematics)

   We consider arbitrary graphs $$G$$ with $$n$$ vertices and minimum degree at least $$\delta n$$ where $$\delta>0$$ is constant.\\ (a) If the conductance of $$G$$ is sufficiently large then we obtain an asymptotic expression for the cover time $$C_G$$ of $$G$$ as the solution to an explicit transcendental equation.\\ (b) If the conductance is not large enough to apply (a), but the mixing time of a random walk on $$G$$ is of a lesser magnitude than the cover time, then we can obtain an asymptotic deterministic estimate via a decomposition into a bounded number of dense subgraphs with high conductance. \\ (c) If $$G$$ fits neither (a) nor (b) then we give a deterministic asymptotic (2+o(1))-approximation of $$C_G$$. 

   more » « less
4. Universal exploration dynamics of random walks

   https://doi.org/10.1038/s41467-023-36233-5  

   Régnier, Léo; Dolgushev, Maxim; Redner, S.; Bénichou, Olivier (December 2023, Nature Communications)

   Abstract The territory explored by a random walk is a key property that may be quantified by the number of distinct sites that the random walk visits up to a given time. We introduce a more fundamental quantity, the time τ n required by a random walk to find a site that it never visited previously when the walk has already visited n distinct sites, which encompasses the full dynamics about the visitation statistics. To study it, we develop a theoretical approach that relies on a mapping with a trapping problem, in which the spatial distribution of traps is continuously updated by the random walk itself. Despite the geometrical complexity of the territory explored by a random walk, the distribution of the τ n can be accounted for by simple analytical expressions. Processes as varied as regular diffusion, anomalous diffusion, and diffusion in disordered media and fractals, fall into the same universality classes. 

   more » « less
5. Using Bernoulli maps to accelerate mixing of a random walk on the torus

   https://doi.org/10.1090/qam/1668  

   Iyer, Gautam; Lu, Ethan; Nolen, James (June 2024, Quarterly of Applied Mathematics)

   We study the mixing time of a random walk on the torus, alternated with a Lebesgue measure preserving Bernoulli map. Without the Bernoulli map, the mixing time of the random walk alone is $$O(1/\epsilon^2)$$, where $$\epsilon$$ is the step size. Our main results show that for a class of Bernoulli maps, when the random walk is alternated with the Bernoulli map~$$\varphi$$ the mixing time becomes $$O(\abs{\ln \epsilon})$$. We also study the \emph{dissipation time} of this process, and obtain~$$O(\abs{\ln \epsilon})$$ upper and lower bounds with explicit constants. 

   more » « less