 many reproofs and generalisations of the original algorithm to different processes and domain types. Notable in this respect is the work of [@Mi] and [@BB] who consider non-convex domains and [@Sa], who appeals to renewal theory to analyse the growth in $\varepsilon$ of the mean number of steps to completion of the walk-on-spheres algorithm. His method also allows for variants of the algorithm in which the sphere sizes do not need to be optimally inscribed in $D$. Later, [@ST] gives an elementary proof of the $|\!\log \varepsilon|$ bound. Mascagni and co-authors have extensively developed the walk-on-spheres algorithm in applications; see for example [@HMG; @Given2001-lu; @Given2002-vs; @Mackoy2013-es; @Hwang2001-wp].

We break the proof into two parts. In the first part, we analyse the walk-on-spheres process over one step, by considering the distance of the next point in the algorithm from the orthogonal tangent hyperplane of the first point. (Note the existence of a tangent hyperplane requires convexity of the domain.) In the second part of the proof, we use this analysis to build a supermartingale, from which the desired result follows via optional stopping.

For the first part of the proof, we start by introducing notation. For any $x = (x_1, \dots, x_d)\in\mathbb{R}^d$ such that $x_1>0$, let us write $V(x) = \{(z_1, \dots, z_d)\in\mathbb{R}^d\colon z_1>0\}$ for the open half-space containing $x$ and denote its boundary $\partial V(x) = \{(z_1, \dots, z_d)\in\mathbb{R}^d\colon z_1=0\}$. Suppose that we choose our coordinate system so that $x\in D$ is such that $\rho_0 = x = (x_1, 0,\dots, 0)$ and $\partial V(\rho_0)$ is a tangent hyperplane to both $D$ and $S_1$. This assumption comes at no cost as, thanks to isotropy and spatial homogeneity of Brownian motion. Let us define $\zeta_0$, the orthogonal distance of $\rho_0$ from $\partial V(\rho_0)$. With the assumed choice of coordinate system, write $\zeta_0 \coloneqq r_1 =  x_1 = |x| = |\rho_0|$ and define $$\zeta_1 = \min\Bigl\{\varepsilon, \inf_{z\in\part