{'fraction_non_alphanumeric': 0.046216978712490385, 'fraction_numerical': 0.01651705565529623, 'mean_word_length': 3.5894538606403015, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The number of ends of critical branching random walks

We investigate the number of topological ends of the trace of branching random walk (BRW) on a graph, showing that in many symmetric cases there are infinitely many ends. We then describe some BRWs which have just one end, and conclude with some open problems.

Of course, there are cases which are not covered by Theorem 1.1. We highlight several interesting and illuminating examples, finding cases where critical BRW has one end, infinitely many ends, and everything in between.
2 Notation 2.1 The spectral radius and amenability Take a random walk (X n , n ≥ 0) on a graph G with transition kernel P . We shall associate a random walk with its transition kernel; for example, if we say "P is simple random walk on G" we mean that P is the transition kernel corresponding to simple random walk on G.
Recall that the spectral radius of P is defined to be ρ = ρ(P ) = lim sup n→∞ P i (X n = j) 1/n .
It is easy to see that this does not depend on the choice of vertices i and j, due to irreducibility of P . See for example [Woe00] for many more details on the spectral radius of a random walk. We say that a random walk is amenable if ρ(P ) = 1, and non-amenable otherwise 1 . Often we say that a graph G is amenable (non-amenable, respectively), by which we mean that the relevant random walk on G is amenable (non-amenable).
In many cases we will consider simple (isotropic) random walk on a graph G, which jumps to each of its current neighbours with equal probability, and write P G for its transition kernel.

Cartesian products of graphs
It is natural, at first, to restrict ourselves to vertex-transitive graphs. If a graph is amenable then the critical branching random walk is just a random walk, so we are interested in nonamenable graphs. Observe also that if a vertex-transitive graph G has infinitely many ends itself, then the trace of any transient BRW will have infinitely many ends too. Thus we are interested in one-ended, non-amenable, vertex-transitive graphs. A natural way to construct such graphs is to take the Cartesian product of two vertex-transitive graphs, at least one of which is non-amenable 2 .
To be precise, for two graphs G 1 and G 2 (not necessarily vertex transitive), the Cartesian product Given transition kernels P 1 and P 2 on G 1 and G 2 respectively, we can then define a random walk on G 1 × G 2 by flipping a fair coin at every step: if it comes up heads, then we take a step along an edge inherited from G 1 according to P 1 , and if it comes up tails, we take a random walk along an edge inherited from G 2 according to P 2 . We write P = 1 2 P 1 + 1 2 P 2 for the corresponding 1 To avoid possible confusion, we point out that the concept of non-amenability usually refers to graphs which satisfy a certain isoperimetric inequality. Kesten [Kes59] showed that for Cayley graphs of finitely generated groups ρ = 1 if and only if the graph is amenable. This powerful result motivates our terminology.
2 It is a standard result (see for example [Woe00], Theorem 4.10) that the Cartesian product of two vertextransitive graphs is amenable if and only if both factors are amenable. transition kernel. We consider this to be the "natural" random walk on G 1 × G 2 . Note that this is not necessarily the usual isotropic simple random walk on G 1 × G 2 , in which the walk moves to each of its neighbours with equal probability. However, all of our results apply without change in the isotropic case; see Section 6 for details.

T × Z and lazy random walk
Our first example is T 3 × Z, where T 3 is the tree in which every vertex has degree 3. Consider P = 1 2 P T 3 + 1 2 P Z . It is easy to calculate that ρ(P T 3 ) = 2 √ 2/3, and of course ρ(P Z ) = 1. From this we deduce (see Lemma 6.1) that Proposition 3.1. If m µ = 1/ρ(P ), then the trace of BRW(T 3 × Z, µ, P ) has infinitely many ends almost surely.
Proof. Consider the projection of the branching random walk onto T 3 . At each time n ≥ 0, each particle branches independently into a random number of particles with law µ; and each of these particles moves independently according to lazy simple random walk on T 3 ; that is, it stays put with probability 1/2, otherwise it makes a step according to a simple random walk on T 3 . Call the transition kernel for this walk L (so L = P /2 + I/2, where P is simple random walk on T 3 and I is the identity matrix). Then so BRW(T 3 , µ, L) is a critical branching random walk and therefore transient. We deduce that each copy of Z is hit only finitely often by particles in BRW(T 3 × Z, µ, P ); since T 3 has infinitely many ends, this property is inherited by the trace of the branching random walk.
Note that our proof did not require many detailed properties of the two graphs T 3 and Z. In fact all that we used was that critical BRW on T 3 has infinitely many ends, and that Z is amenable.
4 T 3 × T 3 , purple dots, and a proof of Theorem 1.1 The natural next question is to consider what happens when our Cartesian product is of two non-amenable graphs. We begin with T 3 ×T 3 , and note that our previous tactic no longer works. Each copy of T 3 is hit infinitely often by particles of the critical BRW, which tells us nothing about the number of ends of the trace. We instead look from a different viewpoint: if we start two independent critical branching random walks from vertices a long way apart, do they meet? Start one critical BRW from a vertex i ∈ T 3 × T 3 , and call this the red process; start the other, independent critical BRW from vertex j, and call it the blue process. Colour red any vertex that is hit by a particle in the red process, and colour blue any vertex that is hit by a particle in the blue process. Vertices that are coloured both red and blue we call purple. We are interested in the number of purple vertices. For this we will need some detailed estimates on the return probability of simple random walk on T 3 × T 3 , and a simple tool for calculating expected numbers of particles in branching processes. We delay these details for a moment to show that Proposition 4.1 is enough to establish that the trace of critical BRW on T 3 × T 3 has infinitely many ends.
Proposition 4.2. Let P be simple random walk on T 3 × T 3 , and suppose that m µ = 1/ρ(P ). Then the trace of BRW(T 3 × T 3 , µ, P ) has infinitely many ends almost surely.
Proof (assuming Proposition 4.1). For every n ≥ 0 define N (n) to be the set of particles alive in the branching random walk at time n. Now fix k > 0, and let T = inf{n ≥ 0 : |N (n)| ≥ k}, the first time that we have more than k particles alive (since m > 1 and µ(0) = 0, T < ∞ almost surely). Label these particles 1, . . . , |N (T )|. For each particle r at time T , given its position, its descendants draw out a BRW; call this BRW r . Note that, by Proposition 4.1, the intersection of the trace of BRW r with the trace of BRW s is finite for each r = s. Thus the particles of BRW r form at least one topological end distinct from the particles of s =r BRW s . We deduce that we have at least k ends almost surely. Since k was arbitrary, we must have infinitely many ends.
We now list the technical results that we need to prove Proposition 4.1. We say that P( The following lemma is due to Cartwright and Soardi [CS86, Theorem 2i)]. Slight variations can also be found in [GW86] and [Woe86].
Lemma 4.3. If T is the homogeneous tree in which every vertex has exactly d ≥ 3 neighbours, and X n is a simple random walk on T , then for any vertex i, there exists a constant C i such that where ρ is the spectral radius of the random walk.
Combining this with another result of Cartwright and Soardi [CS87], included in full generality in Section 6 as Lemma 6.1, gives us the following corollary.
Corollary 4.4. If X n , n ≥ 0 is simple random walk on T 3 × T 3 , then for any vertex i, there exists a constant C i such that Finally, we will use the following well-known result about branching random walks 3 . Consider a BRW(G, µ, P ). Let N (n) be the set of particles alive in the branching random walk at time n, and for u ∈ N (n), write Z(u) for its position in G.
Lemma 4.5 (Many-to-one). For any i,j and n, We can now prove Proposition 4.1, which said that the expected number of purple vertices is finite when we start red and blue independent critical BRWs from vertices i and j respectively, for any choice of i and j in T 3 × T 3 .
Proof of Proposition 4.1. Let N R (n) be the set of particles in the red BRW at time n, and 3 The proof of this simple version is an easy exercise. Much stronger versions are known. N B (n) the set of particles in the blue BRW at time n. Then, by Lemma 4.5, where under P i,j , X and X are independent simple random walks started from i and j respectively. But by the symmetric nature of our random walk, We now use Corollary 4.4, which tells us that P i (X k = j) ∼ Cρ k /k 3 . Since m = ρ −1 , we obtain Having proved Proposition 4.1, and thus established that critical branching random walk on T 3 × T 3 has infinitely many ends, we now ask ourselves what properties of the graph we used for this result, and whether we can generalise it. In fact the only property we used, besides the obviously necessary assumption ρ < 1, was that P i,j (X k = X n ) ≤ CP i (X k+n = j) for some constant C, which is true whenever X n , n ≥ 0 is quasi-symmetric. Besides, it is easy to check that k,n m k+n P i (X k+n = i) = n (n + 1)m n P i (X n = i).
We have therefore implicitly proved Theorem 1.1.
We remark here that Müller [Mül09] obtained the same condition for ensuring that BRW on a Cayley graph is dynamically stable: that is, if we construct a BRW and then rerandomise each random walk step at rate 1, there is never a time at which the BRW is recurrent.
Relaxing our assumptions even further, we obtain the following.

One-ended branching random walks, and some open problems
It is natural to ask whether a converse of Theorem 1.1 might hold. But we already know that a full converse cannot hold: simple random walk on T 3 × Z satisfies ∞ k,n=0 ρ −(k+n) P(X k+n = 0) = ∞, but the corresponding critical BRW has infinitely many ends.
Can we, then, construct a critical BRW on a non-amenable graph whose trace is one-ended? If we allow ourselves to bias our random walk in one direction, then the answer is yes. (Without a bias, the answer is still yes, but the construction is more difficult and we save it for later.) We return to considering G = T 3 × Z, but this time we bias the random walk so that on Z it is more likely to move in one direction than the other. To be precise, let P 1 be simple random walk on T 3 , and P 2 (p) be the random walk on Z that moves right with probability p and left with probability 1 − p. Let P (p) = 1 2 P 1 + 1 2 P 2 (p).
Proposition 5.1. For P (p) as above with p = 1/2, the trace of critical BRW on T 3 × Z has one end almost surely.
Proof. Just as in the proof that the symmetric case has infinitely many ends, this essentially follows from comparing the spectral radius of lazy random walk on T 3 with the spectral radius of P (p). Indeed, just as in the proof of Proposition 3.1, we have ρ(L) = √ 2/3 + 1/2; but this time ρ(P (p)) = √ 2/3 + p(1 − p) < ρ(L). We deduce that each copy of Z is hit "often enough" that there is only one end; the rest of the proof is concerned with making this statement precise. We resort to the use of purple dots.
Fix a copy of Z; call it Z 0 . We have established that the BRW hits Z 0 infinitely often. Take a realisation of the BRW, and choose two particles. The descendants of the first particle we call red, and the descendants of the second particle we call blue. Any site in Z 0 that is hit by both red and blue particles we colour purple. We show that there are purple sites almost surely (in fact infinitely many of them); this is enough to show that the trace of the BRW has only one end, since the two particles chosen were arbitrary (and the process eventually leaves any large ball).
Let p n be the probability that a biased RW started from a site in Z 0 is in Z 0 at time n; otherwise defined, p n is the return probability of the lazy random walk on T 3 at time n. Since ρ(L) > ρ(P (p)), we can choose k such that p k > ρ(P (p)) k . (1) Fix a red particle in Z 0 . Call it u. Let S u 0 = {u}, and for j ≥ 1 define S u j = {descendants of particles in S u j−1 that are in Z 0 at time jk}.
Let Y u j = |S u j | for each j. Then (Y u j , j ≥ 0) is a Galton-Watson process whose birth distribution λ satisfies E[λ] = ρ(P (p)) −k p k > 1.
Note that the probability of Q u does not depend on the choice of u; let q = P(Q u ) > 0. We choose a red particle in Z 0 via the following algorithm: Take a red particle u 1 in Z 0 . If Q u 1 occurs, then choose u 1 . For each i ≥ 2, If Q u i−1 does not occur, then take a red particle u i in Z 0 \ i−1 l=1 ∞ r=1 S u l r . If Q u i occurs, then choose u i . Since each particle's Galton-Watson process is independent of the others, and each has a fixed probability of surviving forever, the algorithm terminates with probability one; then we have an infinite sequence v 1 , v 2 , . . . of red particles in Z 0 each of which is at distance at most k from another (a random walk cannot move further than distance k in time k), where k satisfies (1). For any particle v, let Y (v) be the projection of that particle's position (in T 3 × Z) onto Z 0 . Since the process is transient, by taking a subsequence and re-ordering if necessary, we may assume that Similarly we can construct an increasing sequence of blue particles w 1 , w 2 , . . . in Z 0 with spacing at most k (where k is such that (1) is satisfied). From these two sequences of particles, we see that there are infinitely many pairs of red and blue particles within distance k/2 of each other. Since the RW has a positive probability of stepping upwards k/2 times in a row, there exists some δ > 0 such that each pair has probability at least δ of generating a purple vertex independently of the others. Thus we must have infinitely many purple vertices, which completes the proof.
On T 3 × T 3 , the situation is more complicated. We introduce a bias on one of the factors as shown in Figure 1: a rigorous description follows. Choose an isometric embedding φ : Z → T 3 ; that is, choose a two-sided infinite path in T 3 and label the vertices on that path . . . , −2, −1, 0, 1, 2, . . .. For each vertex i in T 3 , we give it a height h(i) = arg min k d(i, φ(k)) − min k d(i, φ(k)). If we view φ as labelling certain vertices in T 3 , then h(i) is the label of the closest vertex in φ(Z) minus the graph distance between i and φ(Z). Note that each vertex with height h has two neighbours of heights h + 1 and one of height h − 1. Now define a random walk P p on T 3 which jumps from a vertex with height h to its neighbour of height h − 1 with probability p, and to each of its neighbours of height h + 1 with probability (p − 1)/2. LetP p = 1 2 P p + 1 2 P T 3 . Suppose that for each p, m µ(p) = 1/ρ(P p ).
Proof. The first statement follows from exactly the same argument as Proposition 3.1. The second is almost identical to Proposition 5.1, except that we have to look at a copy of Z embedded in T 3 .
What if we insist that our random walk is isotropic? Can we construct a graph on which the corresponding critical BRW is one-ended? Again, the answer is yes. Let N 0 = {0, 1, 2, . . .}, and let T be the rooted tree in which every vertex has four children, and every vertex except the root has one parent. We say that the root has generation 0, its children have generation 1, and so on. Construct a graph H by joining n ∈ N 0 to every vertex in generation n and every vertex in generation n + 1 in T, for each n ≥ 0. We call H the hammock graph.
By coupling with a random walk on Z that jumps right with probability 4/7 and left with probability 3/7, we see that ρ(P H ) < 1. Starting at the root o of T, by repeatedly jumping to generation 1 and then back to the root, we get P (X 2n = o) ≥ (4/5) n (1/7) n so ρ(P H ) > 0. Showing that the critical BRW is one-ended can be done in a very similar way to the proof of Proposition 5.1. Choose any two particles in the BRW, and colour their descendants red and blue respectively; any site hit by both a red and a blue particle is coloured purple. Clearly a random walk on H eventually hits N 0 almost surely, so N 0 is hit infinitely often by red particles and infinitely often by blue particles. We can ensure (for example by constructing embedded Galton-Watson processes as in the proof of Proposition 5.1) that there are almost surely infinitely many red-blue pairs within distance at most k of each other. Each of these pairs has at least a fixed probability δ > 0 of creating a purple dot (since this time N 0 does not have bounded degree, we have to allow particles to bounce back and forth between N 0 and T). Thus we have infinitely many purple dots almost surely, and since our initial choice of red and blue particles was arbitrary, this guarantees that we have only one end.
Remark 5.4. By gluing together various copies of graphs already constructed, it is easy to construct graphs on which critical BRW has any number of ends. For example, if we glue two copies of H and one copy of T 3 × T 3 at a single vertex, then we have a graph on which critical BRW has one end, two ends, or infinitely many ends, each with positive probability.
Open problem. Does there exist a quasi-symmetric random walk such that the corresponding critical BRW is one-ended almost surely?
Another possibility for future research is to investigate the Cayley graphs of co-compact Fuchsian groups. These graphs correspond to tilings of the hyperbolic plane. Lalley and Sellke [LS97] showed that critical branching Brownian motion on the hyperbolic plane has a limit set that does not have full measure, and by analogy one might expect that critical branching random walks on co-compact Fuchsian groups have infinitely many ends.
Finally, we relay a conjecture from Itai Benjamini.
Conjecture 5.5 (Itai Benjamini, private communication). On any vertex-transitive graph G, the trace of simple critical BRW has infinitely many ends.
6 Appendix on product random walks As we mentioned briefly in Section 2, given random walks on d graphs G 1 , . . . , G d , there is more than one natural random walk on G 1 × . . . × G d . Rather than overcomplicate matters with general definitions in the earlier sections, we concentrated on one such natural choice. Here we give more details, and see that in fact our results hold regardless of the choice.
The following lemma, due to Cartwright and Soardi [CS87], tells us how to translate results about return probabilities on certain graphs into results about return probabilities on their Cartesian products. We recall that the Cayley graph G(Y ) of a group Y with generating set S has as its vertex set the elements of Y , with two vertices i, j ∈ Y joined by an edge if i = js for some s ∈ S. We write that P(X n = i) ∼ b n if P(X n = i)/b n → 1 as n → ∞ through values such that P(X n = i) > 0.
Note in particular that the choice of α 1 , . . . , α d affects the spectral radius in the obvious way, and has no effect on the polynomial terms. Thus the proofs in earlier sections are unaffected by choosing different α 1 , . . . , α d . For example, the results on T 3 × Z where we used 1 2 P T 3 + 1 2 P Z hold also for 3 5 P T 3 + 2 5 P Z , which corresponds to simple isotropic random walk on T 3 × Z.