Back to search

University of British Columbia

The hunter-rabbit game with random rabbit graph

Abstract

dc:description

Hunter-Rabbit is a pursuit–evasion game played on the integers from 1 to n, where the hunter attempts to capture the rabbit in as few moves as possible. The hunter is restricted to moving only ±1 at each time step, while the rabbit is allowed more freedom in its movement. Sharp bounds on the expected capture time (𝔼[τ]) have been established in the case where the rabbit moves on the complete graph Kn, which allows it to jump to any vertex at each turn. In this paper, we extend the classical setting by considering the rabbit restricted to a random subgraph of Kn, aiming to determine whether similar asymptotic bounds can still be obtained under these constraints. We prove that, up to constant factors, the same sharp bounds for 𝔼[τ] continue to hold when the game involves a constant number of rabbits and a hunter who is able to catch a rabbit from a greater distance than in the original formulation. We further explore a dynamic version of the game, where the graph governing the rabbit’s movement evolves over time, and we make progress on bounding the capture time in this setting as well. Finally, we show that the problem of identifying a near-optimal evasion strategy for the rabbit on a random graph can be reduced to finding a weighted perfect matching in a related random bipartite graph, thereby providing a new approach to solving this game.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Mathematics
Grantor dc:publisher
University of British Columbia
Year dc:date
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Renault, Joshua
Contributors dc:contributor
  • Angel, Omer

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/92222

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Renault, Joshua. The hunter-rabbit game with random rabbit graph. master's thesis, University of British Columbia, 2025. http://hdl.handle.net/2429/92222