{'fraction_non_alphanumeric': 0.06526067872818755, 'fraction_numerical': 0.023573493202012633, 'mean_word_length': 3.684184133988567, 'pattern_counts': {'":': 0, '<': 56, '<?xml version=': 0, '>': 16, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 34, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Patterns in random walks and Brownian motion

We ask if it is possible to find some particular continuous paths of unit length in linear Brownian motion. Beginning with a discrete version of the problem, we derive the asymptotics of the expected waiting time for several interesting patterns. These suggest corresponding results on the existence/non-existence of continuous paths embedded in Brownian motion. With further effort we are able to prove some of these existence and non-existence results by various stochastic analysis arguments. A list of open problems is presented.


Introduction and main results
We are interested in the question of embedding some continuous-time stochastic processes (Z u , 0 ≤ u ≤ 1) into a Brownian path (B t ; t ≥ 0), without time-change or scaling, just by a random translation of origin in spacetime. More precisely, we ask the following: Question 1.1. Given some distribution of a process Z with continuous paths, does there exist a random time T such that (B T +u − B T ; 0 ≤ u ≤ 1) has the same distribution as (Z u , 0 ≤ u ≤ 1)?.
The question of whether external randomization is allowed or not, is of no importance here. In fact, we can simply ignore Brownian motion on [0, 1], and consider only random times T ≥ 1. Then (B t ; 0 ≤ t ≤ 1) provides an independent random element which is adequate for any randomization.
Note that a continuous-time process whose sample paths have different regularity, e.g. fractional Brownian motion with Hurst parameter H = 1 2 , cannot be embedded into Brownian motion. Given (B t ; t ≥ 0) standard Brownian motion, we define g 1 := sup{t < 1; B t = 0} the time of last exit from 0 before t = 1, and d 1 := inf{t > 1; B t = 0} the first hitting time of 0 after t = 1. The following processes, derived from Brownian motion, are of special interest.
• The Vervaat transform of Brownian motion, defined as where τ := argmin 0≤t≤1 B t , and the Vervaat transform of Brownian bridge with negative endpoint λ < 0 where (b λ u ; 0 ≤ u ≤ 1) is Brownian bridge ending at λ ∈ R and τ := argmin 0≤t≤1 b λ t . The Brownian bridge, meander, excursion and the three-dimensional Bessel process are well-known. The definition of the co-meander is found in Yen and Yor [88,Chapter 7]. The first passage bridge is studied by Bertoin et al [6]. The Vervaat transform of Brownian bridges and of Brownian motion are extensively discussed in Lupu et al [55]. According to the above definitions, the distributions of the Brownian bridge, excursion and (co-)meander can all be achieved in Brownian motion provided some Brownian scaling operation is allowed. Note that the distributions of all these processes are singular with respect to Wiener measure. So it is a non-trivial question whether copies of them can be found in Brownian motion just by a shift of origin in spacetime. Otherwise, for a process (Z t , 0 ≤ t ≤ 1) whose distribution is absolutely continuous with respect to that of (B t , 0 ≤ t ≤ 1), for instance the Brownian motion with drift Z t := ϑt + B t for a fixed ϑ, the distribution of Z can easily be obtained as that of (B T +t − B T , 0 ≤ t ≤ 1) for a suitable stopping time T + 1 by the acceptance-rejection method. We refer readers to Section 3.5 for further development.
The question raised here has some affinity to the question of embedding a given onedimensional distribution as the distribution of B T for a random time T . This Skorokhod embedding problem traces back to Skorokhod [78] and Dubins [20] -who found integrable stopping times T such that the distribution of B T coincides with any prescribed one with mean 0 and finite second moment. Monroe [62,63] considered embedding of a continuoustime process into Brownian motion, and showed that every semi-martingale is a time-changed Brownian motion. We refer readers to the excellent survey of Obloj [67], with a rich body of references. Let X t := (B t+u − B t ; 0 ≤ u ≤ 1) for t ≥ 0 be the moving-window process associated to Brownian motion. In Question 1.1, we are concerned with the possibility of embedding a given distribution on C[0, 1] as that of X T for some random time T . Indeed, Question 1.1 is the Skorokhod embedding problem for the C[0, 1]-valued Markov process X.
Let us present the main results of the paper. We start with a list of continuous-time processes that cannot be embedded into Brownian motion by a shift of origin in spacetime. (1) There is no random time T such that (B T +u −B T ; 0 ≤ u ≤ 1) has the same distribution as (e u ; 0 ≤ u ≤ 1); (2) There is no random time T such that (B T +u −B T ; 0 ≤ u ≤ 1) has the same distribution as (|b 0 u |; 0 ≤ u ≤ 1); (3) There is no random time T such that (B T +u −B T ; 0 ≤ u ≤ 1) has the same distribution as (V u ; 0 ≤ u ≤ 1); (4) For each fixed λ < 0, there is no random time T such that (B T +u − B T ; 0 ≤ u ≤ 1) has the same distribution as (F λ,br u ; 0 ≤ u ≤ 1); (5) For each fixed λ < 0, there is no random time T such that (B T +u − B T ; 0 ≤ u ≤ 1) has the same distribution as (V λ u ; 0 ≤ u ≤ 1).
As we will see later in Theorem 1.6, Theorem 1.2 is an immediate consequence of the fact that typical paths of normalized excursion, reflected bridge, Vervaat transform of Brownian motion, first passage bridge and Vervaat bridge cannot be achieved in Brownian motion. The next theorem shows the possibility of embedding into Brownian motion some continuous-time processes whose distributions are singular with respect to Wiener measure. Theorem 1.3. (Existence of meander, co-meander and 3-d Bessel process) For each of the following three processes Z := (Z u , ≤ u ≤ 1) there is some random time T such that (B T +u − B T ; 0 ≤ u ≤ 1) has the same distribution as Z: (1) the meander Z = (m u ; 0 ≤ u ≤ 1); (2) the co-meander Z = ( m u ; 0 ≤ u ≤ 1); (3) the three-dimensional Bessel process Z = (R u ; 0 ≤ u ≤ 1).
The problem of embedding Brownian bridge b 0 into Brownian motion is treated in a subsequent work of Pitman and Tang [70]. Since the proof relies heavily on Palm theory of stationary random measures, we prefer not to include it in the current work.
There exists a random time T ≥ 0 such that (B T +u − B T ; 0 ≤ u ≤ 1) has the same distribution as (b 0 u ; 0 ≤ u ≤ 1).
In Question 1.1, we seek to embed a particular continuous-time process Z of unit length into a Brownian path. The distribution of X resides in the infinite-dimensional space C[0, 1] of continuous paths on [0, 1] starting from 0. So a closely related problem is whether a given subset of C[0, 1] is hit by the path-valued moving-window process X t := (B t+u −B t ; 0 ≤ u ≤ 1) indexed by t ≥ 0. We formulate this problem as follows.
Question 1.5. Given a Borel measurable subset S ⊂ C[0, 1], can we find a random time T such that X T := (B T +u − B T ; 0 ≤ u ≤ 1) ∈ S with probability one? Question 1.5 involves scanning for patterns in a continuous-time process. As far as we are aware, the problem has yet been studied. Here are some examples of subsets of C[0, 1] : • E is the set of excursion paths, which first returns to 0 at time 1, • RER is the set of reflected bridge paths, i.e.
• FP λ is the set of first passage bridge paths at fixed level λ < 0, i.e.
• VB − is the set paths of Vervaat transform of Brownian motion with a floating negative endpoint, i.e.
• VB λ is the set of Vervaat bridge paths ending at fixed level λ < 0, i.e.
An elementary argument shows that the probability that a given set S ⊂ C[0, 1] is hit by the path-valued process generated by Brownian motion is either 0 or 1, i.e.
Using various stochastic analysis tools, we are able to show that Theorem 1.6. (Non-existence of excursion, reflected bridge, Vervaat transform of Brownian motion, first passage bridge and Vervaat bridge paths) (1) Almost surely, there is no random time T such that (2) Almost surely, there is no random time T such that (3) Almost surely, there is no random time T such that (4) For each λ < 0, almost surely, there is no random time T such that (5) For each λ < 0, almost surely, there is no random time T such that In the current work, we restrict ourselves to continuous paths in linear Brownian motion. However, the problem is also worth considering in the multi-dimensional case, see e.g. Section 4 for further discussions.
At first glance, neither Question 1.1 nor Question 1.5 seems to be tractable. To gain some intuition, we start by studying the analogous problem in the random walk setting. We deal with simple symmetric random walks SW (n) of length n with increments ±1 starting at 0. A typical question is how long it would take, in random walks, to observe certain element in a collection of patterns of length n satisfying some common properties. More precisely, Question 1.7. Given for each n a collection A n of patterns of length n, what is the order of the expected waiting time ET (A n ) until some element of A n is observed in a random walk?
We are not aware of any previous study on pattern problems in which some natural definition of the collection of patterns is made for each n ∈ N. Nevertheless, this question fits into the general theory of runs and patterns in a sequence of discrete trials. This theory dates back to work in 1940s by Wald and Wolfowitz [83] and Mood [64]. Since then, the subject has become important in various areas of science, including industrial engineering, biology, economics and statistics. In 1960s, Feller [26] treated the problem probabilistically by identifying the occurrence of a single pattern as a renewal event. By the generating function method, the law of the occurrence times of such patterns is entirely characterized. More advanced study of the occurrence of patterns in a collection developed in 1980s by two different methods. Guibas and Odlyzko [34], and Breen et al [10] followed the steps of Feller [26] by studying the generating functions in pattern-overlapping regimes. An alternative approach was adopted by Li [54], and Gerber and Li [31] using martingale arguments. We also refer readers to the book of Fu and Lou [29] for Markov chain embedding approach regarding multi-state trials.
Techniques from the theory of patterns in i.i.d. sequences provide general strategies to Question 1.7. Here we focus on some special cases where the order of the expected waiting time is computable. As we will see later, such asymptotics help us predict the existence or non-existence of some particular patterns in Brownian motion. We introduce some discrete patterns as analogs of sets of continuous paths as above. For λ ∈ R, let λ n = [λ √ n] if [λ √ n] and n have the same parity, and λ n = [λ √ n]+1 otherwise. We make the following definitions: • E 2n is the set of discrete positive excursions of length 2n, whose first return to 0 occurs at time 2n, i.e.
As in Question 1.7, T (A n ) is the waiting time until some pattern in A n appears in the simple random walk for A n ∈ {E 2n , M 2n+1 , BR λ,n , FP λ,n }. The following result answers Question 1.7 in these particular cases. (1) There exists C E > 0 such that (1.1) Now we explain how the asymptotics obtained in Theorem 1.8 help to answer, at least formally, Question 1.1 and Question 1.5 in some cases. Formula (1.1) tells that it would take on average n 3 2 n steps to observe an excursion in simple random walk. In view of the usual scaling of random walks to converge to Brownian motion, the time scale appears to be too large. Thus we should not expect to find excursion pattern E in a Brownian path. However, in (1.2) and (1.3), the typical waiting time to observe a positive walk or a bridge has the same order n involved in the time scaling for convergence in distribution to Brownian motion. So we can anticipate to observe the positive-path pattern M and the bridge pattern BR λ in Brownian motion. Finally in (1.4), there is an exponent gap in evaluating the expected waiting time to have first passage walks ending at λ n ∼ [λ √ n] for λ < 0. In this case, we do not know whether it would take asymptotically n steps or much longer to first observe such patterns. This prevents us from predicting the existence of the first passage bridge pattern FP λ in Brownian motion.
The scaling arguments used in the last paragraph are quite intuitive but not rigorous since we are not aware of any theory which would justify the existence or non-existence of continuous paths by taking limits from the discrete setting.
Organization of the paper: The rest of the paper is organized as follows.
• In Section 2, we study the asymptotic behavior of the expected waiting time for discrete patterns. There Theorem 1.8 is proved. • In Section 3, we are devoted to the analysis of continuous paths/processes in Brownian motion. Proofs of Theorem 1.3 and Theorem 1.6 are provided. • In Section 4, we discuss the potential theory for continuous paths in Brownian motion.
A selection of open problems is presented in Section 2.5 and Section 4.

Expected waiting time for discrete patterns
The current section is devoted to the proof of Theorem 1.8. We study the expected waiting time for some collection of patterns A n ∈ {E 2n , M 2n+1 , BR λ,n , FP λ,n } as defined in the introduction. Note that all patterns in the collection A n have the same length. More precisely, we are interested in the asymptotic behavior of ET (A n ) as the common length of patterns n → ∞.
We start by recalling the general strategy to compute the expected waiting time for discrete patterns in simple random walks. For A n := {A n 1 , · · · , A n k(A n ) }, denote T (A n i ) the waiting time for the A n i renewal and T (A n ) the waiting time till some A n i ∈ A n is renewed, see e.g. Feller [26,Chapter XIII] for general background on renewal strings/patterns.
Define the matching matrix M (A n ), which accounts for the overlapping phenomenon among patterns within the collection A n . The coefficients are given by where l (A n i , A n j ) is defined for A n i := A n i1 · · · A n in and A n j := A n j1 · · · A n jn as for 0 ≤ l ≤ n−1. Note that in general for i = j, M (A n ) ij = M (A n ) ji and hence the matching matrix M (A n ) is not necessarily symmetric. The following result, which can be read from Breen et al [10] is the main tool to study the expected waiting time for the collection of patterns.
Theorem 2.1. [10] (1) The matching matrix M (A n ) is invertible and the expected waiting times for patterns in A n := {A n 1 , · · · , A n k(A n ) } are given by (2) The expected waiting time till one of the patterns in A n is observed is given by In Section 2.1, we apply the previous theorem to obtain the expected waiting time for discrete excursions E 2n , i.e. (1) of Theorem 1.8. The same problem for positive walks M 2n+1 , bridge paths BR 0,2n and first passage walks FP λ,n through λ n ∼ λ √ n, i.e. (2)−(4) of Theorem 1.8, is studied respectively in Section 3.8−2.4. Finally, we discuss the exponent problem for certain discrete patterns in Section 2.5.
2.1. Expected waiting time for discrete excursions. For n ∈ N, the number of discrete excursions of length 2n is equal to the n − 1 th Catalan number, see e.g. Stanley [80,Exercise 6.19 Note that discrete excursions never overlap since the starting point and the endpoint are the only two minima. We have then (E n i , E n j ) = δ ij for 1 ≤ i, j ≤ k(E 2n ) by (2.2). Thus, the matching matrix defined as in (2.1) for discrete excursions E 2n has the simple form According to Theorem 2.1, 2.2. Expected waiting time for positive walks. Let n ∈ N. It is well-known that the number of non-negative walks of length 2n + 1 is 2n n , see e.g. Larbarbe and Marckert [50] and Leeuwen [53] for modern proofs. Thus the number of positive walks of length 2n + 1 is given by Now consider the matching matrix M (M 2n+1 ) defined as in (2.1) for positive walks M 2n+1 . M (M 2n+1 ) is no longer diagonal since there are overlaps among positive walks. Nevertheless, the following result unveils the particular structure of such matrix.
is the multiple of some right stochastic matrix (whose row sums are equal to 1) with multiplicity where k(M l ) := #M l is the number of positive walks of length l as in (2.7).
Proof: Let 1 ≤ i ≤ k(M 2n+1 ) and consider the sum of the i th row where for 0 ≤ l ≤ 2n and M 2n+1 (2.10) In addition, for 1 ≤ l ≤ 2n, jl is a positive walk of length l.

2.3.
Expected waiting time for bridge paths. In this part, we deal with the expected waiting time for the set of discrete bridges. In order to simplify the notations, we focus on the set of bridges of length 2n which ends at λ = 0, i.e. BR 0,2n . Note that the result in the general case for BR λ,n , where λ ∈ R, can be derived in a similar way. Using Theorem 2.1, we prove a weaker version of (1.3), i.e. there exist c 0 BR and C 0 BR > 0 such that Compared to (1.3), there is an exponent gap in (2.13) and the lower bound is not optimal. Nevertheless, the lower bound of (1.3) follows a soft argument by scaling limit, Proposition 2.4. We defer the discussion to Section 2.5. It is standard that the number of discrete bridges of length 2n is (2.14) Denote BR 0,2n := {BR 2n 1 , · · · , BR 2n k(BR 0,2n ) } and M (BR 0,2n ) the matching matrix of BR 0,2n . We first establish the LHS estimate of (2.13). According to (2.3), we have Note that the matching matrix M(BR 0,2n ) is non-negative with diagonal elements . As a direct consequence, the column sums of M (BR 0,2n ) is larger or equal to 1. Then by (2.4) and (2.15), where k(BR 0,2n ) is defined as in (2.14). Take then c 0 BR = √ π − for arbitrary small > 0. Now we establish the RHS estimate of (2.13). In view of (2.15), it suffices to work out an upper bound for the column sums of M (BR 0,2n ). Similarly as in (2.9), for 1 ≤ j ≤ k(BR 0,2n ), = #{discrete bridges of length l which ends at where the last inequality is due to the fact that l k ≤ l [l]/2 for 0 ≤ k ≤ l. By (2.16) and (2.17), the column sums of M (BR 0,2n ) is bounded from above by Again by (2.4) and (2.15), Hence we take C 0 BR = 4 + for arbitrary small > 0.
2.4. Expected waiting time for first passage walks. We consider the expected waiting time for first passage walks through λ n ∼ λ √ n for λ < 0. Following Feller [26, Theorem 2, Chapter III.7], the number of patterns in FP λ,n is For FP λ,n := {F P n 1 , · · · , F P n k(F P λ,n ) } and M (FP λ,n ) the matching matrix for FP λ,n , we have, by (2.3), that The LHS bound of (1.4) can be derived in a similar way as in Section 2.3, i.e.
For the upper bound of (1.4), we aim to obtain an upper bound for the column sums of l (F P n i , F P n j ) = #{F P n i ∈ FP λ,n ; F P n i1 = F P n j1+l , · · · , F P n in−l = F P n jn }.
Observe that {F P n i ∈ FP λ,n ; F P n i1 = F P n j1+l , · · · , F P n in−l = F P n jn } = ∅ if and only if l k=1 F P n jk < 0 (otherwise n−l k=1 F P n ik = n k=1+l F P n jk = λ n − l k=1 F P n jk < λ n , which implies F P n i / ∈ FP λ,n ). Then given F P n i1 = F P n j1+l , · · · , F P n in−l = F P n jn and l k=1 F P n jk < 0, (2.21) From the above discussion, it is easy to see for 1 ≤ j ≤ k(FP λ,n ), where F P n j * is defined as follows: The rest of this part is devoted to estimating Thus, the column sums of M (FP λ,n ) is bounded from above by 8λ π n , We take then C λ F P = 4 λ exp λ 2 2 + for arbitrary small > 0.
2.5. Exponent gaps for BR λ,n and FP λ,n . It can be inferred from (2.13) (resp. (1.4)) that the expected waiting time for BR λ,n where λ ∈ R (resp. FP λ,n where λ < 0) is bounded from below by order n 1 2 (resp. n) and from above by order n (resp. n 5 4 ). The exponent gap in the estimates of first passage walks FP λ,n is frustrating, since we do not know whether the waiting time is exactly of order n, or is of order n. This prevents the prediction of the existence of first passage bridge patterns FP λ in Brownian motion.
From (2.4), we see that the most precise way to compute ET (BR λ,n ) and ET (FP λ,n ) consists in evaluating the sum of all entries in the inverse matching matrices M (BR λ,n ) −1 and M (FP λ,n ) −1 . But the task is difficult since the structures of M (BR λ,n ) and M (FP λ,n ) are complex, at least more inoperable than those as of M (E 2n ) and M (M 2n+1 ). We do not understand well the exact form of its inverse matrix M (BR λ,n ) −1 and M (FP λ,n ) −1 .
The technique used in Section 2.3 and Section 2.4 is to bound the column sums of the matching matrix M (BR λ,n ) (resp. M (FP λ,n )). More precisely, we have proved that (2.23) For the bridge pattern BR 0,2n , the LHS bound of (2.22) is obtained by any excursion path of length 2n, while the RHS bound of (2.22) is achieved by the sawtooth path, with consecutive ±1 increments. In the first passage pattern FP λ,n where λ < 0, the LHS bound of (2.23) is attained by some excursion-like paths, which start by excursions and go linearly to λ √ n < 0 at the end. The RHS bound of (2.23) is given by the extreme pattern defined in Section 2.4, see e.g. Figure 1.
However, all above estimations are not accurate, since there are only few columns in BR λ,n (resp. FP λ,n ) which sum up either to O(1) (resp. O(1)) or to O(n (1) determine the exact asymptotics for ET (BR λ,n ) where λ ∈ R, as n → ∞; (2) determine the exact asymptotics for ET (FP λ,n ) where λ < 0, as n → ∞.
As we prove below, for λ ∈ R, ET (BR λ,n ) n by a scaling limit argument. Nevertheless, to obtain this result only by discrete analysis would be of independent interest. The following table provides the simulations of the expected waiting time ET (FP −1,n ) for some large n. The result strongly suggests the existence of a real number ζ ∈ (1, 5 4 ) such that ET (FP −1,n ) n ζ . This is confirmed by Theorem 1.6 (4), that is we cannot find a first passage bridge with fixed negative endpoint in Brownian motion.
where n 2 is the next to n 1 in the table. Now let us focus on the lower bound (1.3) of expected waiting time for bridge pattern BR 0 . For n ∈ 2N, we run a simple random walk (RW k ) k∈N until the first level bridge of length n appears. That is, we consider The process (S t := B t+1 − B t ; t ≥ 0) is a stationary Gaussian process, first studied by Slepian [79] and Shepp [77]. The following result, which can be found in Pitman and Tang [70,Lemma 2.3], is needed for the proof of Proposition 2.4.
Proof of Proposition 2.4: Let P W be Wiener measure on C[0, ∞). Let P S (resp. P W ) be the distribution of the Slepian process S (resp. the distribution of B defined as in (2.26)). We claim that F := inf{t ≥ 0; w t+1 = w t }, is a functional of the coordinate process w := {w t ; t ≥ 0} ∈ C[0, ∞) that is continuous P W a.s. Note that the distribution of (x t := w t+1 − w t ; t ≥ 0) under P W is the same as that of (w t ; t ≥ 0) under P S . In addition, x ∈ C[0, ∞) is a functional of w ∈ C[0, ∞) that is continuous P W a.s. By composition, it is equivalent to show that is a functional of w ∈ C[0, ∞) that is continuous P S a.s. Consider the set where Z p := {G ∈ [p, p + 1] and F is not a continuous functional of w ∈ C[0, ∞)}. It is obvious that P W (Z) = 0 and thus P W (Z p ) = 0 for all p ≥ 0. By Lemma 2.5, P S is locally absolutely continuous relative to P W , which implies that P S (Z p ) = 0 for all p ≥ 0. As a countable union of null events, P S (Z) = 0, and the claim is proved. Thus, the mapping is continuous P W a.s. According to Donsker's theorem [19], see e.g. Billingsley [9,Section 10] Note that T (BR 0,n ) = F n + n. Following the above analysis, we know that T (BR 0,n )/n converges weakly to F + 1, where T (BR 0,n ) is the waiting time until an element of BR 0,n occurs in a simple random walk and F is the random time defined as in (2.25). As a consequence, lim inf n→∞ E T (BR 0,n ) n ≥ (EF + 1), since EF < ∞.
In particular, EF ≤ C 0 BR − 1 = 3 as in Section 2.3. We refer readers to Pitman and Tang [70] for further discussion on first level bridges and the structure of the Slepian zero set.

Continuous paths in Brownian motion
This section is devoted to the proof of Theorem 1.3 and Theorem 1.6 regarding continuous paths and the distribution of continuous-time processes embedded in Brownian motion. In Section 3.1, we show that there is no normalized excursion in a Brownian path, Theorem 1.6 (1). A slight modification of the proof allows us to exclude the existence of the Vervaat bridges with negative endpoint, Theorem 1.6 (5). Furthermore, we prove in Section 3.2 that there is even no reflected bridge in Brownian motion, Theorem 1.6 (2). In Section 3.3 and 3.4, we show that neither the Vervaat transform of Brownian motion nor first passage bridges with negative endpoint can be found in Brownian motion, i.e. Theorem 1.6 (3) (4). We make use of the potential theory of additive Lévy processes, which is recalled in Section 3.3. Finally in Section 3.5, we provide a proof for the existence of Brownian meander, comeander and three-dimensional Bessel process in Brownian motion, i.e. Theorem 1.3, using the acceptance-rejection method.

No normalized excursion in a Brownian path.
In this part, we provide two proofs for (1) of Theorem 1.6, though similar, from different viewpoints. The first proof is based on a fluctuation version of Williams' path decomposition of Brownian motion, originally due to Williams [84], and later extended in various ways by Millar [59,60], and Greenwood and Pitman [33]. We also refer readers to Pitman and Winkel [71] for a combinatorial explanation and various applications. Then H and R are independent exponential variables, each with the same rate ϑ. Furthermore, conditionally given H and R, the path (B t ; 0 ≤ t ≤ ξ) is decomposed into two independent pieces: is Brownian motion with drift −ϑ < 0 running until it first hits the level −R < 0. Now we introduce the notion of first passage process, which will be used in the proof of (1) of Theorem 1.6. Given a real-valued process (Z t ; t ≥ 0) starting at 0, we define the first passage process (τ −x ; x ≥ 0) associated to X to be the first time that the level −x < 0 is hit: When Z is Brownian motion, the distribution of the first passage process is well-known. It can be obtained either by random walks approximation or by Itô's excursion theory [36]. (1) Let W be Wiener measure on C[0, ∞). Then the first passage process (τ −x ; x ≥ 0) under W is a stable( 1 2 ) subordinator, with (2) For ϑ ∈ R, let W ϑ be the distribution of Brownian motion with drift ϑ. Then for each fixed L > 0, on the event τ −L < ∞, the distribution of the first passage process (τ −x ; 0 ≤ x ≤ L) under W ϑ is absolutely continuous with respect to that under W, with density D ϑ L := exp(−ϑL − ϑ 2 2 τ −L ). Proof of Theorem 1.6 (1): Suppose by contradiction that P(T < ∞) > 0, where T is the first time that some excursion pattern appears. Take ξ exponentially distributed with rate 1 2 , independent of (B t ; t ≥ 0). We have then Now (T, T + 1) is inside the excursion of Brownian motion above its past-minimum process, which straddles ξ. Define • (σ −x ; x ≥ 0) to be the first passage process of (B ξ−t −B ξ ; 0 ≤ t ≤ ξ −M ) concatenated by an independent Brownian motion with drift −1 running forever ; • (τ −x ; x ≥ 0) to be the first passage process of (B ξ+t − B ξ ; t ≥ 0). x ≥ 0) is the first passage process of Brownian motion with drift −1, whose distribution is absolutely continuous on any compact interval [0, L], with respect to that of (τ −x ; 0 ≤ x ≤ L) by part (2) It is easy to see that the above argument still works for proving the non-existence of the Vervaat bridge pattern VB λ , with endpoint λ < 0.
Proof of Theorem 1.6 (5): We borrow the notations from the preceding proof. Observe that, for fixed λ < 0, P(σ −x + τ −x+λ = 1 for some x ≥ 0) = 0. The rest of the proof is just a duplication of the preceding one.
We give yet another proof of Theorem 1.6 (1), which relies on Itô's excursion theory, combined with Bertoin's self-similar fragmentation theory. For general background on fragmentation processes, we refer to the monograph of Bertoin [5]. The next result, regarding a normalized Brownian excursion, follows Bertoin [4, Corollary 2].

Theorem 3.3. [4]
Let e := (e u ; 0 ≤ u ≤ 1) be normalized Brownian excursion and F e := (F e t ; t ≥ 0) be the associated interval fragmentation defined as F e t := {u ∈ (0, 1); e u > t}. Introduce • λ := (λ t ; t ≥ 0) the length of the interval component of F e that contains U , independent of the excursion and uniformly distributed; • ξ := {ξ t ; t ≥ 0} a subordinator, the Laplace exponent of which is given by Then (λ t ; t ≥ 0) has the same law as (exp(−ξ ρt ); t ≥ 0), where Alternative proof of Theorem 1.6 (1): Consider the reflected process (B t − B t ; t ≥ 0), where B t := inf 0≤u≤t B u is the past-minimum process of the Brownian motion. For e the first excursion of B − B that contains some excursion pattern E of length 1, let Λ e be the length of such excursion, and e * be the normalized Brownian excursion. Following Itô's excursion theory, see e.g. Revuz and Yor [72,Chapter XII], Λ e is independent of the distribution of the normalized excursion e * . As a consequence, the fragmentation associated to e * produces an interval of length 1 Λe . Now choose U uniformly distributed on [0, 1] and independent of the Brownian motion. According to Theorem 3.3, there exists a subordinator ξ characterized as in (3.2) and a time-change ρ defined as in (3.3) such that (λ t ; t ≥ 0), the process of the length of the interval fragmentation which contains U , has the same distribution as (exp(−ξ ρt ); t ≥ 0). Note that (λ t ; t ≥ 0) depends only on the normalized excursion e * and U , so (λ t ; t ≥ 0) is independent of Λ e . It is a well known result of Kesten [39] that a subordinator without drift does not hit points. Therefore, for some t ≥ 0 = 0, which yields the desired result.

No reflected bridge in a Brownian path.
This part is devoted to proving Theorem 1.6 (2). The main difference between Theorem 1.6 (1) and (2) is that the strict inequality B T +u > B T for all u ∈ (0, 1) is relaxed by the permission of equalities B T +u = B T for some u ∈ (0, 1). Thus, there seems to be more chance to find the reflected bridge paths RBR in Brownian motion. Nevertheless, the following lemma suggests that one cannot expect the equality to be achieved for more than one instant in between. Below is a slightly stronger version of this result. It is straightforward that T ⊂ U. In addition, it is well-known that almost surely Brownian motion has a unique minimum on any fixed interval [s, t] for all s, t ∈ R. As a countable union of null events, P(U) = 0 and thus P(T ) = 0.
Remark 3.5. The previous lemma has an interesting geometric interpretation in terms of Brownian trees, see e.g. Pitman [68,Section 7.4] for background. Along the lines of the second proof of Theorem 1.6 (1) in Section 3.1, we only need to show that the situation in Lemma 3.4 cannot happen in Brownian excursion either of an independent and diffuse length or of normalized unit length. But this is just another way to state that Brownian trees have only binary branch points, which follows readily from Aldous' stick-breaking construction of the continuum random trees, see e.g. Aldous [1,Section 4.3] and Le Gall [51].
According to Theorem 1.6 (1) and Lemma 3.4, we see that almost surely, there are neither excursion paths nor reflected bridge paths with at least two reflections in Brownian motion. To prove the desired result, it suffices to exempt the possibility of reflected bridge paths with exactly one reflection. Lemma 3.6. Assume that 0 ≤ S < T < U are random times such that B S = B T = B U and B u > B S for u ∈ (S, T ) ∪ (T, U ). Then the distribution of U − S is absolutely continuous with respect to the Lebesgue measure.
Proof: Suppose by contradiction that the distribution of U − S is not absolutely continuous with respect to the Lebesgue measure. Then there exists p, q ∈ Q such that U − S fails to have a density on the event {S < p < T < q < U }. In fact, if U − S has a density on {S < p < T < q < U } for all p, q ∈ Q, Radon-Nikodym theorem guarantees that U − S has a density on {S < T < U } = ∪ p,q∈Q {S < p < T < q < U }. Note that on the event {S < p < T < q < U }, U is the first time after q such that the Brownian motion B attains inf u∈[p,q] B u and obviously has a density. Again by Radon-Nikodym theorem, the distribution of U − S has a density on {S < p < T < q < U }, which leads to a contradiction.
Remark 3.7. The previous result can also be inferred from a fine study on local minima of Brownian motion. Neveu and Pitman [66] studied the renewal structure of local extrema in a Brownian path, in terms of Palm measure, see e.g. Kallenberg [38,Chapter 11] for background. More precisely, denote • C to be the space of continuous paths on R, equipped with Wiener measure W; • E to be the space of excursions with lifetime ζ, equipped with Itô measure n.
Then the Palm measure of all local minima is the image of 1 2 (n × n × W) by the mapping E × E × C (e, e , w) →w ∈ C given bỹ Using the notations of Lemma 3.6, an in-between reflected position T corresponds to a Brownian local minimum. Then the above discussion implies that U − S is the sum of two independent random variables with densities and hence is diffuse. See also Tsirelson [81] for the i.i.d. uniform sampling construction of Brownian local minima, which reveals the diffuse nature of U − S.
In Section 3.1, we showed that for each fixed λ < 0, there is no random time T such that (B T +u − B T ; 0 ≤ u ≤ 1) ∈ VB λ . However, there is no obvious way to pass from the non-existence of the Vervaat bridges to that of the Vervaat transform of Brownian motion, due to an uncountable number of possible levels.
To get around the problem, we make use of an additional tool -potential theory of additive Lévy processes, developed by Khoshnevisan et al [41,42,46,47,45]. We now recall some results of this theory that we need in the proof of Theorem 1.6 (3). For a more extensive overview of the theory, we refer readers to the survey of Khoshnevisan and Xiao [43]. Theorem 3.9. [47,86,45] Let (Z t ; t ∈ R N + ) be an additive Lévy process defined as in (3.4). Then where Leb(·) is the Lebesgue measure on R d , and Re(·) is the real part of a complexe number.
The next result, which is read from Khoshnevisan and Xiao [44,Lemma 4.1], makes a connection between the range of an additive Lévy process and the polarity of single points. See also Khoshnevisan and Xiao [43, Lemma 3.1].

3.4.
No first passage bridge in a Brownian path. We prove Theorem 1.6 (4), i.e. there is no first passage bridge in Brownian motion by a spacetime shift. The main difference between Vervaat bridges with fixed endpoint λ < 0 and first passage bridges ending at λ < 0 is that the former start with an excursion piece, while the latter return to the origin infinitely often on any small interval [0, ], > 0. Thus, the argument used in Section 3.1 to prove the non-existence of Vervaat bridges is not immediately applied in case of first passage bridges. Nevetheless, the potential theory of additive Lévy processes helps to circumvent the difficulty.
Combining with (3.8), we obtain: It is well-known that time reversal of Brownian first passage bridge ending at λ < 0, i.e.
(F λ,br 1−u + |λ|; 0 ≤ u ≤ 1) has the same distribution as three dimensional Bessel bridge ending at |λ| > 0, see e.g. Biane and Yor [8]. It is not hard to see that the above argument still works for δ-dimensional Bessel bridges with δ ≥ 2, where {0} is polar. In particular, there is no random time T ≥ 0 such that (B T +u − B T ; 0 ≤ u ≤ 1) has the same distribution as δ-dimensional Bessel bridge ending at λ, with δ ≥ 2.
3.5. Meander, co-meander and 3-d Bessel process in a Brownian path. We prove Theorem 1.3 in this section using Itô's excursion theory, combined with Rost's filling scheme [11,73] solution to the Skorokhod embedding problem.
The existence of Brownian meander in a Brownian path is assured by the following wellknown result, which can be read from Maisoneuve [57,Section 8], with explicit formulas due to Chung [13]. An alternative approach was provided by Greenwood and Pitman [32], and Pitman [69,Section 4 and 5]. See also Biane and Yor [7,  Theorem 3.13. [57,69,7] Let (e i ) i∈N be the sequence of excursions, whose length exceeds 1, in the reflected process (B t − B t ; t ≥ 0). Then (e i u ; 0 ≤ u ≤ 1) i∈N is a sequence of independent and identically distributed paths, each distributed as Brownian meander (m u ; 0 ≤ u ≤ 1).
Let us recall another basic result due to Imhof [35], which establishes the absolute continuity relation between Brownian meander and the three-dimensional Bessel process. Their relation with Brownian co-meander is studied in Yen and Yor [88,Chapter 7].
Theorem 3.14. [35,88] The distributions of Brownian meander (m u ; 0 ≤ u ≤ 1), Brownian co-meander ( m u ; 0 ≤ u ≤ 1) and the three-dimensional Bessel process (R u ; 0 ≤ u ≤ 1) are mutually absolutely continuous with respect to each other. For F : C[0, 1] → R + a measurable function, According to Theorem 3.13, there exist T 1 , T 2 , · · · such that form a sequence of i.i.d. Brownian meanders. Since Brownian co-meander and the threedimensional Bessel process are absolutely continuous relative to Brownian meander, it is natural to think of von Neumann's acceptance-rejection algorithm [82], see e.g. Rubinstein and Kroese [75,Section 2.3.4] for background and various applications. However, von Neumann's selection method requires that the Radon-Nikodym density between the underlying probability measures is essentially bounded, which is not satisfied in the cases suggested by Theorem 3.14. Nevertheless, we can apply the filling scheme of Chacon and Ornstein [11] and Rost [73]. We observe that sampling Brownian co-meander or the three-dimensional Bessel process from i.i.d. Brownian meanders (m i ) i∈N fits into the general theory of Rost's filling scheme applied to the Skorokhod embedding problem. In the sequel, we follow the approach of Dellacherie and Meyer [18,Chapter IX], which is based on the seminal work of Rost [73], to construct a stopping time N such that m N achieves the distribution of m or R. We need some notions from potential theory for the proof. (1) Given a Markov chain X := (X n ) n∈N , a function f is said to be excessive relative to X if (f (X n )) n∈N is F n − supermartingale, where (F n ) n∈N is the natrual filtrations of X.
where µ m i (1) is the total mass of the measure µ m i . It is not hard to see that the bounded excessive functions of the i.i.d. meander sequence are constant µ m a.s. Since µ R is absolutely continuous with respect to µ m , for each µ m a.s. constant function c, µ R (c) = µ m (c) = c. Consequently, µ R is a balayage/sweeping of µ m by Definition 3.15. According to Theorem 69 of Dellacherie and Meyer [18], Now let d 0 be the Radon-Nikodym density of µ m 0 relative to µ m , and for i > 0, d i be the Radon-Nikodym density of µ m i relative to µ m i−1 (1) · µ m . We have (3.12) Consider the stopping time N defined by where (d i ) i∈N is the sequence of Radon-Nikodym densities defined as in the preceding paragraph, (m i ) i∈N is the sequence of i.i.d. Brownian meanders defined as in (3.9), and ξ is exponentially distributed with rate 1, independent of (m i ) i∈N . From the computation of (3.12), for all bounded measurable function f and all k ∈ N, are the filling measures defined as in (3.10) and (3.11). By summing over all k, we have E[f (m N ); N < ∞] = µ R f, i.e. m N has the same distribution as R. As a summary, where (T i ) i∈N is defined by (3.9) and N is the stopping time as in (3.13). Thus we have achieved the distribution of the three-dimensional Bessel process in Brownian motion. The existence of Brownian co-meander is obtained in the same vein. The problem whether Brownian co-meander or the three-dimensional Bessel process can be embedded in finite expected time, remains open. More generally, Rost [74] was able to characterize all stopping distributions of a continuous-time Markov process, given its initial distribution. In our setting, let (P t ) t≥0 be the semi-group of the moving window process X t := (B t+u − B t ; 0 ≤ u ≤ 1) for t ≥ 0, and µ W be its initial distribution, corresponding to Wiener measure on C[0, 1]. Following Rost [74], for any distribution µ on C[0, 1], one can construct the continuous-time filling measures (µ t , µ W t ) t≥0 and a suitable stopping time T such that µ − µ t + µ W t = µ W P t∧T . Thus, the distribution µ is achieved if and only if µ ∞ = 0, where µ ∞ :=↓ lim t→∞ µ t . In particular, Brownian motion with drift (ϑt + B t ; 0 ≤ t ≤ 1) for a fixed ϑ, can be obtained for a suitable stopping time T + 1.

Potential theory for continuous-time patterns
In Question 1.5, we ask for any Borel measurable subset S of C[0, 1] whether S is hit by the moving-window process X t := (B t+u − B t ; 0 ≤ u ≤ 1 for t ≥ 0, at some random time T . Related studies of the moving window process appear in several contexts. Knight [48,49] introduced the prediction processes, where the whole past of the underlying process is tracked to anticipate its future behavior. The relation between Knight's prediction processes and our problems is discussed briefly at the end of the section. Similar ideas are found in stochastic control theory, where certain path-dependent stochastic differential equations were investigated, see e.g. the monograph of Mohammed [61] and Chang et al [12]. More recently, Dupire [21] worked out a functional version of Itô's calculus, in which the underlying process is path-valued and notions as time-derivative and space-derivative with respect to a path, are proposed. We refer readers to the thesis of Fournié [28] as well as Cont and Fournié [15,16,17] for further development. Indeed, Question 1.5 is some issue of potential theory. In Benjamini et al [2] a potential theory was developed for transient Markov chains on any countable state space E. They showed that the probability for a transient chain to ever visit a given subset S ⊂ E, is estimated by Cap M (S) -the Martin capacity of the set S. See also Mörters and Peres [65, Section 8.3] for a detailed exposition. As pointed out by Steven Evans [24], such a framework still works well for our discrete renewal patterns. For 0 < α < 1, define the α−potential of the discrete patterns/strings of length n as where , ∈ {−1, 1} n , and P (·, ·) is the transition kernel of discrete patterns/strings of length n in simple random walks, and σ k (resp. τ k ): {−1, 1} n → {−1, 1} n−k the restriction operator to the last n − k strings (resp. to the first n − k strings). The following result is a direct consequence of the first/second moment method, and we leave the detail to readers. . Now let us mention some previous work regarding the potential theory for path-valued Markov processes. There has been much interest in developing a potential theory for the Ornstein-Uhlenbeck process in Wiener space C[0, ∞), defined as Z t := U (t, ·) for t ≥ 0, where U (t, ·) := e −t/2 W (e t , ·) is the Ornstein-Uhlenbeck Brownian sheet. Note that the continuous-time process (Z t ; t ≥ 0) takes values in the Wiener space C[0, ∞) and starts at Z 0 := W (1, ·) as standard Brownian motion. Following Williams [85], a Borel measurable set S ⊂ C[0, ∞) is said to be quasi-sure if P(∀t ≥ 0, Z t ∈ S) = 1, which is known to be equivalent to Cap OU (S c ) = 0, is the Fukushima-Malliavin capacity of S c , that is the probability that Z hits S c before an independent exponential random time with parameter 1. Taking advantage of the well-known Wiener-Itô decomposition of the Ornstein-Uhlenbeck semigroup, Fukushima [30] provided an alternative construction of (4.1) via the Dirichlet form. The approach allows the strengthening of many Brownian almost sure properties to quasi-sure properties. See also the survey of Khoshnevisan [40] for recent development.
Note that the definition (4.2) can be extended to any (path-valued) Markov process. Within this framework, a related problem to Question 1.5 is is the usual path-concatenation, then P(∃T > 0 such that X T ∈ S] = 0, i.e. almost surely the set S is not hit by the moving-window process X. Otherwise, P[∃T ∈ [0, t] such that X T ∈ S] > 0 for some t ≥ 0, and an elementary argument leads to P[∃T ≥ 0 such that X T ∈ S] = 1.
As context for this question, we note that path-valued Markov processes have also been extensively investigated in the superprocess literature. In particular, Le Gall [52] characterized the polar sets for the Brownian snake, which relies on earlier work on the potential theory of symmetric Markov processes by Fitzsimmons and Getoor [27] among others.
There has been much progress in the development of potential theory for symmetric pathvalued Markov processes. However, the shifted process, or the moving-window process, is not time-reversible and the transition kernel is more complicated than that of the Ornstein-Uhlenbeck process in Wiener space. So working with a non-symmetric Dirichlet form, see e.g. the monograph of Ma and Röckner [56], seems to be far from obvious. Open problem 4.2.
(1) Is there any relation between the two capacities Cap X and Cap M W on Wiener space? (2) Propose a non-symmetric Dirichlet form for the shifted process (Θ t • B) t≥0 , which permits to compute the capacities of the sets of paths E, M, BR λ . . .etc.
This problem seems substantial already for one-dimensional Brownian motion. But it could of course be posed also for higher dimensional Brownian motion, or a still more general Markov process. Following are some well-known examples of non-existing patterns in ddimensional Brownian motion for d ≥ 2.
We refer readers to the book of Mörters and Peres [65, Chapter 9 and 10] for historical notes and further discussions on sample path properties of Brownian motion in all dimensions. Finally, we make some connections between Knight's prediction processes and our problems. For background, readers are invited to Knight [48,49] as well as the commentary of Meyer [58] on Knight's work. To avoid heavy measure theoretic discussion, we restrict ourselves to the classical Wiener space (C[0, ∞), F, (F t ) t≥0 , P W ), where (F t ) t≥0 is the augmented Brownian filtrations satisfying the usual hypothesis of right-continuity.
The prediction process is defined as, for all t ≥ 0 and S ∞ a Borel measurable set of C[0, ∞), is the shifted path defined as in (4.3). Note that (Z W t ) t≥0 is a strong Markov process, which takes values in the space of probability measure on the Wiener space (C[0, ∞), F). In terms of the prediction process, Question 1.5 can be reformulated as Question 1.5 : Given a Borel measurable set S ⊂ C[0, 1], can we find a random time T such that EZ W T (S ⊗ 1 C[0, ∞)) = 1? where S ⊗ 1 C[0, ∞) is defined as in (4.4).