{'fraction_non_alphanumeric': 0.06337930716361456, 'fraction_numerical': 0.011508833433276442, 'mean_word_length': 3.4397911120212985, 'pattern_counts': {'":': 0, '<': 64, '<?xml version=': 0, '>': 64, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 29, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Discretisation and Duality of Optimal Skorokhod Embedding Problems

We prove a strong duality result for a linear programming problem which has the interpretation of being a discretised optimal Skorokhod embedding problem, and we recover this continuous time problem as a limit of the discrete problems. With the discrete setup we show that for a suitably chosen objective function, the optimiser takes the form of a hitting time for a random walk. In the limiting problem we then reprove the existence of the Root, Rost, and cave embedding solutions of the Skorokhod embedding problem. The main strength of this approach is that we can derive properties of the discrete problem more easily than in continuous time, and then prove that these properties hold in the limit. For example, the strong duality result gives dual optimisers, and our limiting arguments can be used to derive properties of the continuous time dual functions, known to represent a superhedging portfolio.


Introduction
For a Brownian motion B and a centered probability distribution µ on R with finite second moment, the Skorokhod embedding problem is to find a stopping time τ such that B τ ∼ µ, and (B t∧τ ) t≥0 is UI. (SEP) The problem was first introduced, and solved, by Skorokhod [27,28] and has since proved important for a range of applications in probability theory and mathematical finance. There have been numerous solutions since that of Skorokhod, and we refer the reader to [23] for a survey of all solutions known at the time. Many of these solutions also have some nice optimality properties. For example, two embeddings of particular importance in this paper are the so-called Root and Rost embeddings, which are the stopping times with minimal/maximal variance respectively that solve the Skorokhod embedding problem. Both of these stopping times are actually hitting times of regions in space by a Brownian motion, and these are the types of solution we focus on here. In this paper we consider optimal Skorokhod embedding problems of the form sup τ E [F (W τ , τ )] over solutions of (SEP) for functions F where it is known that the optimiser is a certain type of hitting time. We discretise this problem to get an infinite linear programming problem which has a well-defined dual and where we are able to prove a strong duality result. For the optimal primal solution we can show that the discrete solution is also of the form of a hitting time, and then in the limit we can recover the continuous time embedding results of, for example, the Root and Rost solutions from [9,24,25,26]. As well as reproving previous results, we can also look at the limit of the dual optimisers and deduce properties of the continuous time dual functions. Indeed, the inspiration for this work was to find the form of the optimal dual solution to an optimal Skorokhod embedding problem which has the financial interpretation of finding an upper bound on the price of a European call option on a leveraged exchange traded fund (LETF), see [11]. It is well known that the dual of such a problem corresponds to finding the minimum cost of a self-financing model-independent superhedging portfolio of the option, and we will explain in Section 3.2 how our discrete dual variables relate to this problem. The stopping time that maximises (OptSEP) when the function F is the payoff of a European call option on an LETF is a hitting time where the stopping region, called a K-cave barrier, introduced in [11], is the combination of a Root barrier and a Rost inverse-barrier. A similar embedding is the cave embedding solution of [4], and we will use this an example throughout this paper since it combines the ideas of both the Root and Rost payoffs and gives some insight into the K-cave problem.
In [4], the authors use ideas from martingale optimal transport, which is closely tied to the Skorokhod embedding problem, to show a monotonicity principle which can be used to to prove the existence of all known optimal solutions of (SEP). The monotonicity principle for an optimal Skorokhod embedding problem links to the idea of c-cyclical monotonicity in optimal transport theory and both of these are based on a notion of path-swapping. This is also how we prove the form of the stopping times in the discrete problems in this paper, as can be seen in Section 4.
The use of discrete systems in model-independent finance is a common theme, see for example [1,2,3,5,7,17,18,21] among others, however the exact nature of our problem, and the passage from discrete to continuous setups, appears to be novel.
The paper is organised as follows: in Section 2 we set up the discrete linear programming problem by discretising (OptSEP). The dual problem is introduced in Section 3 and we give ideas on how this relates to the continuous time dual after proving a strong duality result. In Section 4 we show that the discrete optimal stopping region exhibits the same barrier-type properties as its continuous counterpart. Section 5 focuses on the convergence of the discrete problem back to (OptSEP). In Section 5.1 we show that we can discretise a feasible solution of (OptSEP) and then recover the same stopping time in the limit. Finally in Section 5.2 we prove that our discrete stopping region converges to a continuous stopping region with the same properties, and therefore that the a limit of the discrete optimal solutions is an optimiser of (OptSEP).

Discretisation and Primal Formulation
Consider an atomic measure µ with bounded support, so in particular it has a highest and lowest atom, i.e. ∃x * , x * such that x * is the smallest x > 0 such that µ((x, ∞)) = 0, and x * < 0 is the largest x such that µ((−∞, x * )) = 0. To embed this distribution into a Brownian motion (BM) with a uniformly integrable stopping time, we know that we will stop immediately if we hit x * or x * , so we have absorbing barriers at these levels. We can split the interval [x * , x * ] into a uniform mesh (x N j ) j , for j = {0, 1, . . . , L(N )}, where N is a parameter that we let go to infinity to reduce our mesh size and regain the continuous time case. Now run a Brownian motion, W , stopping every time we hit a level x N j , and consider the process formed by this. In other words, consider the process for k ≥ 0. We will later use Donsker's theorem to recover our Brownian motion, and to ensure we can do this we need to choose the correct mesh size. We let If our Brownian motion has some stopping rule τ , then the discrete process also has some rulẽ τ , defined to be the time t such that τ N t−1 < τ ≤ τ N t . We consider the probabilities If our continuous process starts at x N j * , for some j * , then we have that p j * ,0 = 1, p j,0 = 0 for any j ∈ J \ {j * }, and q j,0 = 0 for all j. We also consider absorbing upper and lower barriers, so p j N 0 ,t , p j N L ,t = 0 for all t. If there exists a maximiser τ of (OptSEP), we can discretise a Brownian motion with this stopping rule to create a random walk as above. This random walk will be a martingale and will embed some distribution µ N , so the p, q associated to this stopping rule will be feasible solutions to the following problem: If F is the function in (OptSEP) we are trying to maximise, thenF will be a discrete version of F chosen so thatF N √ N x , N t → F (x, t).
Note that for two different paths ω,ω, we could have for example τ N 3 (ω) < τ N 2 (ω), which means that in physical time, q j,3 could be stopping mass before q j,2 . We will return to this limiting behaviour later, but for know we think instead of P as describing the dynamics of a random walk on a fixed grid (x N j , t N n ). The choice of our grid should be such that we can regain a Brownian motion in the limit as N → ∞, and since we can quickly verify that t N n = n N is the correct time-step choice. The aim of this discretisation is to allow us to appeal to primal-dual results in linear programming theory to learn something about the properties of the continuous time primal solution, and also our continuous time 'dual', the superhedging problem. The primal problem P is an infinite problem, and so standard strong duality results do not apply. One option is to cut off our problem at some finite time T , use linear programming theory on this finite problem, and then recover our infinite time problem through letting T → ∞. To avoid this extra limiting argument, we keep the infinite time scale, and instead work with a modified version of P that will give an equivalent optimal value, but allows us to use results from infinite-dimensional programming.
These results rely largely on the existence of interior feasible points, and so our new problem must have inequality constraints. To allow this we drop the q variables from the formulation and instead just think of q j,t = 1 2 (p j−1,t−1 + p j+1,t−1 ) − p j,t . We also change the embedding condition to a potential function constraint, requiring that the potential function of the terminal distribution of our process lies above that of µ N . For Brownian motion we know that In particular, if τ embeds a distribution with potential function greater than that of µ, then E [L x τ (B)] ≤ −U µ (x) + U 0 (x). The discrete time analogue of the local time accrued at x N j is, in this case, t p j,t , and so this condition becomes ∞ t=0 p j,t ≤ U j , where U j is defined below. We will assume that U j > 0 for every j, and we also know that each U j is finite, which tells us immediately that (p j,t ) ∈ l 1 when we consider it as an infinite sequence. For the conditions of strong duality we need to work with a smaller set than l 1 , but we later show that our smaller space forms a set of stopping times which are dense in the set of stopping times from the l 1 problem, and we can recover the result in l 1 . The idea is that we restrict ourselves to (p j,t ) ∈ l 1 (π −1 ) := (p j,t ) j,t : j,t p j,t π −1 j,t < ∞ , where π j,t are the values of p we get from running the random walk and stopping only when we hit the boundaries j = j N 0 , j N L . It will be useful to know more about these probabilities π j,t so that we know how the p j,t must decay.
Note that there will be many points at which we must have π = 0 since the random walk simply cannot visit them, for example π j,t = 0 whenever |j − j * | > t, and also we can only visit every other point at each x-level, depending on whether the time is odd or even. To make sense of these in our problem we simply do not include π j,t as a variable for these points.
Lemma 2.1. The sequence (π j,t ) of probabilities π j,t = P Y N t = x N j , t < H x * ∧ H x * is in l 1 , and in particular, there is a vector (m j ) j such that for each j, π j,t ρ t → m j as t → ∞.
Proof. We can of course argue that (π j,t ) ∈ l 1 since t≥0 π j,t = U π j for U π the appropriate potential function, but we give a proof which allows us to deduce something of the form of the π j,t .
Consider running the random walk with the above absorbing region up until some time t, where we have some distribution of the remaining mass. Paths at time t leaving the centre-most point, call itĵ, take longest to be absorbed at the barriers, but all mass leaving this point will be absorbed in a finite time almost surely. In particular, if we fix a small ε > 0, then there is some large M such that P path leaving (ĵ, t) will be absorbed by t + M ≥ ε, or P path leaving (ĵ, t) hasn't been absorbed by t + M ≤ 1 − ε.
By our choice ofĵ, for any s ≥ t + M we have j π j,s ≤ (1 − ε) j π j,t . If we take t = 0, then we know that j π j,0 = 1 and j,0≤r<M π j,r ≤ (L + 1)M , so by the above reasoning, We now have that (π j,t ) ∈ l 1 , and can see that the sequence appears to have some approximate exponential decay.
We have a discrete-time Markov chain on S ∪ {0}, where 0 is our absorbing state (the barriers), and S := {1, . . . , L − 1} is an irreducible set of transient states. We can easily find the leading eigenvalue and corresponding eigenvector of our transition matrix, and this gives us a quasi-stationary distribution for the process. From results on Yaglom limits of periodic Markov chains, see for example Theorem 9 of [14], the q.s.d. has a Yaglom limit. We also know, from standard results, that the survival probability of the process decays exponentially, like ρ t for 0 < ρ < 1 the leading eigenvalue. Combining these results shows that πj,t ρ t → m j , for m j = 2 L sin jπ L > 0 and 0 < ρ = cos π L < 1.
With this result in mind, and for technical reasons, we restrict our (p j,t ) to l 1 (λ) := (p j,t ) j,t : j |p j,t | λ t < ∞ , for some constant λ > ρ −1 > 1. Note here that we are defining l 1 (λ) in such a way that for a fixed t, p j,t is multiplied by λ t for all j. Recall that we are optimising over probabilities (p j,t ) j,t for j ∈ J and t ≥ 1 our discrete time steps, each of length 1 N in continuous time. We choose a j * ,N ∈ J to start our random walk at such that x N j * = j * ,N N → 0 as N → ∞. Our primal problem is then as follows: We leave the conditions at t = 1 as equalities for clarity, but as with the π j,t there will be many points we do not visit at which we must have p = q = 0. We do not include p j,t as a variable for these points. Denote by P N the above problem without the restriction of (p j,t ) ∈ l 1 (λ), i.e. we just require p ∈ l 1 , so P N = P(1) N , and let P N (λ), P N = P N (1) be the optimal values of these two problems. We will show later that P N = P N (λ). We will also introduce dual problems which we will denote by D N (λ), D N with optimal values D N (λ), D N .
where Φ is linear, and A, B are given by 3 Duality

Strong Fenchel Duality
With our choice of primal problem P, we construct a dual problem and show a strong Fenchel duality result using the following theorem from [6, Theorem 4.4.3].
Then p = d, and the supremum in the dual problem is achieved if either of the following hold (i) 0 ∈ core (dom(g) − Adom(f )) and f, g are lower semi-continuous We briefly explain the notation in the theorem, and then use it to prove duality. For a functional f : X → R ∪ {∞}, its convex conjugate is the function f * : As mentioned earlier, we consider X = l 1 (λ) and we think of Y as being R L+1 × l 1 (λ), where the first L + 1 variables correspond to the U j conditions. Elements of Y * = R L+1 × l ∞ λ −1 will be written as y * = (ν j , η j,t ). We take f, g to be and Φ, A, B are as in (2.1). With these functions it is clear that the optimal value p is then −P N (λ). Also, f, g are convex and lower semi-continuous, and A is a linear, bounded operator. The corresponding conjugates are Before showing that these functions satisfy condition (i) of the theorem, we find the dual problem. The dual operator A * is the functional A * : Y * → X * satisfying A * y * , x = y * , Ax ∀x ∈ X. Now, and so, for y * ∈ Y * , .
From this, we see that our Fenchel dual is All that remains to show is that we satisfy one of the two remaining conditions of the theorem.
With A, f, g defined as above, (i) of Theorem 3.1 holds. In particular, there is no duality gap, and the optimiser is attained in the dual problem.
We are required to show that for any z ∈ R L+1 × l 1 (λ) ∃α > 0 and a w of the above form such that αw = z. Take z = (z j , z j,t ) ∈ R L+1 × l 1 (λ), consider a constant, γ, and let ρ k,s j,t = γ |z k,s | 1{s > t} π j,t π k,s , for j, k ∈ J and s, t ≥ 1, so that and similarly for the other terms. Then ρ j,t = k,s ρ k,s j,t ≥ 0 defines a set of probabilities such that, since π ∈ l 1 . Also, for any ε > 0 there is a T such that for every j and t ≥ T , The first sum is a finite sum of finite terms, so is finite, and the second is finite since (z j,t ) ∈ l 1 (λ) ⊂ l 1 (π). Let m = max j m j and m = min j m j . Then for the final sum, again since (z j,t ) ∈ l 1 (λ) ⊂ l 1 (π), and this also has a finite limit as ε → 0.
In particular, we have (ρ j,t ) ∈ l 1 (λ). For each j, t we need y j ≥ −U j , y j,t ≥ 0, γ > 0 and α > 0 such that Setting α = γ −1 , we find that . Now we can see that the scaling factor was necessary to ensure that even if y j is negative, we can scale it so that it is still larger than −U j . Note here that division by zero isn't an issue since t π j,t k,s |z k,s | π k,s is a strict upper bound of t ρ j,t by (3.3) and we can therefore choose a smaller bound if z j = 2 t π j,t k,s

Interpretation of Dual Variables
In this section we outline the interpretation of the dual problem and its relation to the continuous time problem of minimising the cost of superhedging strategies. This work was motivated by the problem of finding a robust upper bound on the price of a European option on a leveraged exchange traded fund, and in particular in [11] we use results from this paper to give the form of the optimal superhedging strategy in that case. Here we give a brief overview of how the continuous time hedging strategy can be obtained from (ν * , η * ), the optimisers of D N (λ). Our Fenchel dual problem is In Lagrangian duality we know that we have duality exactly when the complementary slackness conditions hold, and this is also true here. Fix N and take the optimal dual solution y * = (ν * , η * ) and any primal feasible p, so g(Ap) = 0. Then, We have equality in the above inequalities, and p is a primal optimiser, if and only if the following complementary slackness conditions hold: where as always we define q j,t = 1 2 (p j−1,t−1 + p j+1,t−1 ) − p j,t . It is well known that in the continuous time problem of finding an upper bound on the price of an exotic option that the dual problem corresponds to minimising the cost of a super-replicating portfolio, and much work has been done in finding conditions under which there is no duality gap. In [12] and [13] the authors give the form of the optimal superhedging strategy in the case where the optimal stopping time corresponds to a Root or Rost hitting time. They define functions G(x, t), representing a dynamic trading strategy, and H(x), corresponding to a fixed portfolio of options, in terms of the stopping time/stopping region. If G, H are defined such that for a feasible stopping time σ we have then we have the optimal dual portfolio and no duality gap. The first two conditions above are dual feasibility conditions, and the final two ensure optimality, so we can think of them as complementary slackness conditions. We can then see how we might recover these functions from our dual problem.
We require functions G, H such that G + H is a superhedge, and G(W t , t) is a supermartingale, and these conditions correspond to (3.1) and (3.2) respectively. If we defineη * j,t = η j,t +F N j,t then (3.1), (3.2) becomẽ soη has the superhedging and supermartingale properties we are looking for. It then makes sense to hope that we find lim Our complementary slackness conditions (3.7) and (3.8) then correspond to G(W t , t) being a martingale in the continuation region and having an exact hedge in the stopping region. From (3.7) we have is a martingale and we have the suitable differentiability. Also, our dual objective function then becomes

Strong Duality of P N , D N
We now have strong duality in the λ problems, and attainment in the dual problem. In this section we show that we have primal attainment in P N , the l 1 problem, and that the optimal value in this case agrees with the l 1 (λ) problem, P N = P N (λ).
Lemma 3.3. ChooseF N so that P N < ∞. Then P N = P N (λ) and the supremum P N is attained by some sequence p * ∈ l 1 .
Proof. To show primal attainment in P N , we show that the feasible region of P N is a compact subset of l 1 , and therefore supremums are attained. It is well known that a metric space is compact if it is totally bounded and complete. We argue that completeness of our feasible region follows from the formulation of P N , in particular we have no strict inequalities, so if the limit of a sequence of feasible solutions exists, then it will also be feasible. To show total boundedness we use the Kolmogorov-Riesz Compactness Theorem equivalent for l p spaces from [16], first proved in [15].
Theorem. A subset of l r , where 1 ≤ r < ∞, is totally bounded if and only if, (i) it is pointwise bounded, and (ii) for every ε > 0 there is some n so that, for every x in the given subset, It is clear that our sequences are pointwise bounded, but also note that for any sequence (p j,t ) in our feasible region, we have that p j,t ≤ π j,t ∀(j, t), so in particular, j,t>n p j,t ≤ j,t>n π j,t .
Our strong duality result, Theorem 3.1, proves that D N (λ) = P N (λ), but we also have weak duality in the original discretised problem, so D N ≥ P N , where D N (λ) is the value of our dual problem taking (ν, η) ∈ R L+1 × l ∞ (λ −1 ), and D N is the optimal dual value with (ν, η) ∈ R L+1 × l ∞ . Also, Let p * be an optimiser of P N , whose existence we have just proven. Since l 1 (λ) ⊆ l 1 , we either have that p * ∈ l 1 (λ), or we can 'cut-off' p * at some finite time, and we get a feasible solution to P N (λ). Define p T j,t = p * j,t 1{t < T }, then we have an approximating sequence, (p T ) T , of feasible solutions of P N (λ), with j,tF N j,t q T j,t → j,tF N j,t q * j,t provided j,tF N j,t q * j,t < ∞. We must therefore have P N = P N (λ).
Remark 3.4. If (ν * , η * ) are the optimisers of D N (λ) then, similarly to above, we can consider . Then (ν,η T ) are D N -feasible for large T and certainF N .
An important example is whereF N is the discretisation of some European call option which is decreasing in time. In this case there is some T * such thatF N j,t = 0 for all t ≥ T , and then we find D N = D N (λ) and (ν,η T ) attain D N for any T > T * . This is the case of the leveraged exchange traded fund payoff from [11].

The Cave Embedding Case
So far we have made no assumptions on our functions F,F N except that they give well-defined optimisation problems, and thatF N → F in some sense. We now show that for certain choices of F , these discrete optimisation problems have certain properties that have already been shown in the continuous time case. In particular, we focus on the ideas of the Root, Rost, and cave embeddings, first given in [24], [25], and [4] respectively. We concentrate on the cave embedding example, since it is a combination of a Root barrier and a Rost inverse-barrier, and therefore incorporates the arguments of the other two problems. Recall from [4] that a region R ⊆ R × R + is a cave barrier if there exists a t 0 ∈ R + , an inverse barrier R 0 ⊆ R × [0, t 0 ], and a barrier R 1 ⊆ R × [t 0 , ∞) such that R = R 0 ∪ R 1 . In [4] it is proved that there exists a cave barrier R such that τ = inf{t ≥ 0 : (W t , t) ∈ R} minimises E[ϕ(σ)] over all stopping times σ such that W σ ∼ µ, where ϕ : R + → [0, 1] is such that • ϕ(0) = 0, lim t→∞ ϕ(t) = 0, ϕ(t 0 ) = 1 • ϕ is strictly concave (and therefore increasing) on [0, t 0 ] • ϕ is strictly convex (decreasing) on [t 0 , ∞).
Fix t 0 ∈ R + and consider our payoff to be the negative of such a function (so that we are still maximising), i.e. F (x, t) = f (t) := −ϕ(t), soF N j,t =f N (t) = −ϕ t N . We argue that our optimal p j,t (we will drop the * now since we will always be thinking about the optimal solutions) define a discretised cave barrier stopping region for the random walk, and that this stopping region embeds exactly our distribution µ N , for each N . If we were working with the primal problem P then it would be clear that we embed µ N , however it appears that this could fail with the conditions of P, since our potential function could sit above that of µ N , so we actually embed a different distribution. From now on we will be working solely with the primal optimisers p * , and so for ease of presentation we will drop the * notation. Recall that we write q j,t := 1 2 (p j−1,t−1 + p j+1,t−1 ) − p j,t . Proof. If we have equality in our potential function condition, then by uniqueness, our stopping rule must embed µ N . To show this, we change our payoff function in a way that doesn't affect our problem or previous arguments, but ensures that it is never optimal to have a strict inequality in our potential condition. We know that if W σ ∼ µ, then E [σ] = x 2 µ(dx) is fixed, and so we can add a linear function of time to our payoff without affecting how the optimum solution is obtained. In particular, this means that in this case we can make our payoff increasing everywhere (at least away from zero), by considering F (x, t)+Ct and thereforef N (t)+C t N for some large constant C. This will change our dual problem, and our interpretations of η * and ν * become G(x, t) + H(x) − F (x, t) + Ct Now if we release mass at some (j, r), sincef N (t) + C t N is increasing, it will go on to score more than its current value, meaning that we always run our process for as long as possible in order to be optimal. If we have some x k such that ∞ t=1 p k,t < U k , then it is easy to see that we can find a site (i, s) such that q i,s > 0 and U i > t p i,t and release some mass from here. Suppose there does not exist such a site (i, s). Then at any j at which we embed mass we have U j = t p j,t . Now, for any j = j * ± 1, t p j,t ≤ t 1 2 (p j−1,t−1 + p j+1,t+1 ) = 1 2 t p j−1,t + 1 2 j,t p j+1,t with equality if and only if no mass is embedded at x N j . Then we have that t p j,t is linear between points j at which we embed mass, which we know is also case in potential functions, and therefore we must have U j = t p j,t everywhere, by the convexity of U . Therefore, by contradiction, we have such a point (i, s). Now fix 0 < ε < min {q i,s , U i − t p i,t }, and definep,q bȳ p j,r = p j,r ,q j,r = q j,r otherwise.
It is easy to check thatp,q are P-feasible, and also j,r . This shows we can always improve our payoff if we do not have equality in the potential condition, and therefore it is never optimal to have a strict inequality in this condition. In particular, by uniqueness of potentials, the optimal p embed µ N into the associated random walk.
Now that we know that we embed the correct distribution, we can actually show that we do this using an almost-deterministic stopping region that has the form of a cave barrier.
Theorem 4.2. The optimal solution of the primal problem P, whereF j,t =f (t) = −ϕ t N for ϕ a cave function, is given by p j,t which give a stopping region for a random walk with the cave barrier-like property if q i,t > 0 for some (i, t) where t > t 0 , then p i,s = 0 ∀s > t.
Proof. First consider the inverse-barrier to the left of t = t 0 . To show this, suppose we have a feasible solution with q i,t > 0 and p i,s > 0 for some i and s < t < t 0 . We take some 0 < ε < min{ 1 2 q i,t , p i,s } and show that we can improve our objective function (increase the payoff), by transferring ε of the mass that currently leaves (i, s) onto (i, t). To move the paths we need to know how this ε of mass behaves, and the following quantities 'track' an ε mass of particles leaving (i, s): p i,s = ε,p j,s = 0 ∀j = i,q j,s = 0 ∀j, p j,r+1 = p j,r+1 × (the ε mass from (j + 1, r) + the ε mass from (j − 1, r)) Using thep,q, and the procedure described here, we can write down thep,q corresponding to the system after the transfer of the mass. Note that in the above, and it what follows, we define p,p, and thenq,q follow from definingq j,t = 1 2 (p j−1,t−1 +p j+1,t−1 ) −p j,t , and similarly forq, but we write them out for clarity. Before time s nothing changes, and so we havē p j,r = p j,r ,q j,r = q j,r ∀(j, r) ∈ {(j, r) : 1 ≤ r < s}.
At s we stop ε particles that previously left (i, s): Between times s and t we have lost these stopped paths, sō p j,r = p j,r −p j,r ,q j,r = q j,r −q j,r ∀(j, r) ∈ {(j, r) : s < r < t}.
At time t we release an extra ε paths that were previously stopped at (i, t), givinḡ For r > t we have the ε paths from (i, t), but we have now lost ε from (i, s), so we havē p j,r = p j,r −p j,r +p j,r−(t−s) ,q j,r = q j,r −q j,r +q j,r−(t−s) ∀(j, r) ∈ {(j, r) : t < r}.
Thesep,q are P N -feasible by Lemma 4.3, and in Lemma 4.4 we show that these do indeed increase our payoff.
The lemmas then tell us that whenever we have a primal-feasible solution p where there exists i and s < t such that q i,t > 0 and p i,s > 0, we can improve optimality by moving mass between these points. In particular, since we know by linear programming theory that an optimiser exists, our optimal p cannot have this property, so we have a discrete form of an inverse barrier: if q i,t > 0 for some (i, t) where t < t 0 , then p i,s = 0 ∀s < t.
For the barrier to the right of t = t 0 we can repeat the same procedure. Suppose we have a feasible solution with q i,t > 0 and p i,s > 0 for some i and t 0 < t < s. We take some 0 < ε < min{q i,t , 1 2 p i,s } and again transfer ε of the mass that currently leaves (i, s) onto (i, t). To do this we use the samẽ p as above, and definep,q to be the values after the transfer bŷ p j,r = p j,r ,q j,r = q j,r , ∀j, r < t p j,r = p j,r +p j,r+s−t ,q j,r = q j,r +q j,r+s−t , ∀j, t < r < ŝ p i,s = p i,s +p i,2s−t − ε,q i,s = q i,s +q i,2s−t + ε, p j,s = p j,s +p j,2s−t ,q j,s = q j,s +q j,2s−t , ∀j = î p j,r = p j,r +p j,r+s−t −p j,r ,q j,r = q j,r +q j,r+s−t −q j,r , ∀j, r > t.
It is then clear immediately thatp j,r ,q j,r ≥ 0 ∀(j, r) = (i, s). Note thatq i,s ≤ ε 2 and therefore ε < 1 2 q i,s < 2 3 q i,s =⇒q i,s + ε ≤ 3 2 ε < q i,s , so we also have thatq i,s ≥ 0. The new system also embeds the same amount of mass at every level, for example for j = i, we can check that our potential condition will not change:  if q i,t > 0 and p i,s > 0 for some i and s < t < t 0 then f (r)q j,r ≥ f (r)q j,r , if q i,t > 0 and p i,s > 0 for some i and t 0 < t < s then f (r)q j,r ≥ f (r)q j,r .
Proof. Consider first the case of the inverse barrier. We have {r > s} = {r + t − s < t 0 } ∪ {r < t 0 < r + t − s} ∪ {t 0 ≤ r} and in the first region, by the convexity off N on [0, t 0 ]. For r < t 0 < r + t − s, Finally, for t 0 ≤ r, Then by the definition ofq in each of our time regions, we have Briefly, here is how we get the above. For the first line we have just written outp,q in full. We know that we almost surely embed all of the released mass in finite time and so j,rq j,r = ε, and this gives us the fourth equality above. Finally, as we noted above, We can also show that this argument doesn't change if we add a linear function of time to our payoff, as mentioned in Lemma 4.1. Considering nowf (t) + C t N we have, in the notation above, C r>s,j r Nq j,r − C r>t,j r Nq j,r−(t−s) = Cε t−s N , so, For the case of the right-hand barrier, sincef (r) is increasing for r > t 0 , and similarly when we add a linear term.
Remark 4.5. For the corresponding results in the cases whereF N j,t = f ( t N ) for f convex or concave, just consider the Rost or Root parts of the above respectively and the arguments hold exactly.
Remark 4.6. Similarly to Lemma 4.1, if F (x, t) = f (t) and f (t) is bounded, then we can consider f (t) − Ct for some large constant C and show that actually p j,t q j,t = 0 for all (j, t). This is not immediately obvious from Theorem 4.2 since we could have finitely many points at which p j,t > 0, q j,t > 0. Since these points will disappear when we take limits, this isn't an important detail and we omit the proof.

Recovering the Continuous Optimiser
Now we have a full picture for the discrete problem, we can show that the sequence of linear programming problems indeed converges to our continuous problem. We first show that if we discretise the optimal continuous time solution, then we recover it in the limit of the discrete problems produced.
Let τ be a solution of (OptSEP) andτ N the corresponding stopping time of the random walk Y N t as defined earlier to be the time k such that τ N k−1 < τ ≤ τ N k .
Theorem 5.1. For a function F (x, t) continuous in both variables, and a suitable discretisation In particular, when F is bounded, To prove this we use the following lemma.
Lemma 5.2. For theτ N defined above, we have Proof. Note that for any ω, For the stopping time convergence, let M (t) = sup{k : τ N k ≤ T } for any t. We claim that for any T > 0, ε > 0, If this is true, then M (τ ) N P − → τ as N → ∞, but since M (τ ) =τ − 1 we have our result. All that remains is to prove the claim.
Fix T, ε > 0 and let X n = n N − τ N n , so (X n ) n is a martingale. If n 0 is such that M (T ) ≤ n 0 , then Therefore, Choose n 0 = 2T N 3 2 , then P (M (T ) > n 0 ) < ε 3 for all sufficiently large N . Also, X n0 = n0 k=1 X k − X k−1 , the sum of iid mean zero random variables with variance 2 3N 2 . Then, by Doob's martingale inequality, Now we know how Y Ñ τ N andτ N converge, we can prove our theorem.
Proof of Theorem 5.1. Sinceτ but by the convergence ofF N , for any ω and any ε > 0 ∃N ε,ω such that ∀N ≥ N ε,ω , Remark 5.3. This result tells us that if we discretise the optimal continuous time solution, to get some feasible p τ,N j,t , and then take the limit, we recover our optimal value, so in particular, Remark 5.4. Note that as a corollary of Lemma 5.2 we have that µ N = L Y Ñ τ N → L (W τ ) = µ.

Convergence of Barriers
We know that in the case of a cave, Root, or Rost payoff, for each N , P N is attained by some p * ,N which give us a barrier-type property for a random walk. Consider again the cave case, then we know that for each j there is a largest timel N j < t 0 such that p j,t = 0 ∀t ≤l N j , and similarly a smallest timer N j > t 0 such that p j,t = 0 ∀t ≥r N j . For to include the upper and lower boundaries. Denote this stopping region byB N . Note that for each j we either have q j,l N j > 0, or q j,s = 0 ∀s < t 0 , and similarly forr N j . To find the corresponding stopping region for the Brownian motion in continuous time, we shift from discrete to continuous time, so let We now show that the stopped random walks converge to a stopped Brownian motion with the correct distribution, and therefore that P N converges to the continuous time optimal value. Lemma 5.5. The cave barriers B N converge (possibly along a subsequence) to another cave barrier and H x * ∧ H x * is an integrable stopping time, we know that ∀ε > 0 ∃y ε such that P τ N > y ε < ε ∀N , and therefore there is a compact set A ⊆ [x * , x * ] × R + such that ρ N (A) < ε ∀N . In particular, the sequence (ρ N ) is tight, and then by Prokhorov's theorem, there exists some ρ ∞ such that ρ N w − → ρ ∞ (perhaps after restricting to a suitable subsequence). What remains to show is that ρ ∞ (·) = P ((W τ ∞ , τ ∞ ) ∈ ·), and we follow the ideas of [24] and [10].
In [24], Root maps the closed half plane onto a closed, bounded rectangle and defines a norm on the space of closed subsets of the half plane by d(R, S) = sup x∈R inf y∈S r(x, y), where r is the metric induced by taking the Euclidean metric on the rectangle. Under d, the space of closed subsets of our half plane is a separable, compact metric space and the space of all cave barriers is a closed subspace of the space, so is compact. We have a sequence of regions B N , and then by compactness they converge (possibly after taking a further subsequence) to some cave barrier B ∞ in this norm. Denote the hitting time of B ∞ by τ ∞ .
Consider first our Root barrier, and let B N now just denote the barrier part of the stopping region. By [24] we then know that the hitting times of the B N converge to the hitting time of B ∞ in probability as N → ∞, and therefore W τ N for c, where b ∞ is the curve associated to B ∞ . This means we can just consider the part of the Rost inverse-barriers that are in the compact region to the left of the curve K(x), but then in this region we have that the metric r is bounded, and so for any δ > 0, we can find an ε > 0 such that Then, combining the results of [24] and [10] by considering the minimum of the two stopping times, we have that (W τ N , τ N ) Lemma 5.6. With the stopping times defined previously, Proof. We again consider the barrier and inverse-barrier hitting times separately and use the ideas of [24] and [10]. For the Rost inverse-barrier alone we consider the Girsanov Theorem approach of [10]. Fix δ > 0 and some T > 0 and let ε = δ 8x * . Donsker's theorem tells us that for any fixed T there is a Brownian motion B such that P sup = B t ± εt and denote the associated hitting times of B N by τ N,±ε . The Girsanov Theorem tells us that B ε is a Q ε -Brownian motion, where dQε dP Ft = exp εB t − 1 2 ε 2 t , and similarly for B −ε .
It follows that τ N N − τ N d − → 0 as N → ∞, and therefore τ N N − τ N P − → 0 since the limit is a constant. Then, Y N τ N − W τ N P − → 0 also as N → ∞, and therefore for the Rost part of the stopping time we have the required convergence in probability. To see that − W τ N and use Donsker's theorem on the first term and the convergence of the stopping times in the second term. Now consider just the Root barrier and fix ε > 0. We repeat the proof of [24,Lemma 2.4] to show that for any ε > 0, ∃N 0 , n 0 such that N ≥ N 0 , n ≥ n 0 =⇒ P τ N,n −τ N > ε < ε and therefore τ N −τ N,n P − → 0 as N → ∞. Fix ε > 0. Again by Donsker's Theorem, ∃N 0 such that N ≥ N 0 =⇒ P A N,ε > 1− ε 6 . We can choose η > 0 such that P sup η<t<ε B t − ε > η and inf η<t<ε B t + ε > −η > 1 − ε 6 , and therefore for N ≥ N 0 , Since the hitting region with atoms only at j = j N 0 , j N L is an example of a Rost barrier, we know from the above that Y N τ N,π ,τ and so since we are working on a bounded domain, as N → ∞, and also each E τ N,π is bounded. We can therefore find a uniform bound on the E τ N , and in particular ∃T such that, by the Markov Inequality, We can also find N ≥ N 0 , n ≥ n 0 such that d B N ,B n < η, and then can follow exactly the argument of [24, Lemma 2.4] to get that τ N −τ N,n P − → 0 as N, n → ∞. We can use a similar argument to the above to then show that Y N τ N − Y N τ N,n P − → 0, and so Y N τ N ,τ N − Y N τ N,n ,τ N,n P − → 0 as N, n → ∞. Donsker's theorem also shows that for any n, τ N,n N , Y N τ N,n d − → (τ n , W τ n ) as N → ∞, and we prove this in Lemma 5.7. Combining these results and Lemma 5.5 gives the necessary convergence.
Lemma 5.7. If τ n andτ N,n are as defined above, then Proof. By the choice of our discretisation, we know by Donsker's Theorem that (Y N N t ; t ≤ T ) d − → (W t ; t ≤ T ) as N → ∞ for any T > 0, and then by the Portmanteau Theorem, where we consider K to be a subset of the set of continuous paths f ∈ C[0, T ]. Fix n and consider Y N τ N,n and W τ n for N ≥ n. Take some point (t, x n i ) ∈ B n and fix a closed interval,B(ε) = {x n i } × [t − γ, t + γ], of width γ < n −1 around this point. We show that the set of continuous paths which hit B n for the first time inB(ε) is a Borel set. Note that since we are working with discrete barriers, there is a smallest y > x n i such that ({y} × [t − γ, t + γ]) ∩ B n = ∅, and also a largest z < x n i satisfying the same property. Now consider the sets K ε q := {f ∈ C[0, T ] : f (s) < y − ε ∀s ∈ [t − γ, q] ∩ Q} , K ε,δ q := {f ∈ C[0, T ] : f (q) < x n i + δ} ∩ K ε q , K ε,δ := q∈[t−γ,t+γ] q∈Q K ε,δ q , Then, since K ε q , K ε,δ q are Borel, K y is also. Similarly we can define the above when considering z instead of y, with the opposite inequalities, and we would find that K z is Borel. Since our barrier is a closed region, K 1 := {f ∈ C[0, T ] : f doesn't hit B n before time t − γ} is open in C[0, T ], and therefore K := K 1 ∩ (K y ∪ K z ) is a Borel set. But K is exactly the set of paths which hit B n for the first time inB(ε). Now, ∂K is the set of paths which start at 0 and either hitB(ε) at times t ± γ, or hitB(ε) anywhere but also hit B n elsewhere first without passing through any atoms of B n . The probability a Brownian path hits at t ± γ or one of the finite number of end points of the atoms is 0, but if it touches an atom of the boundary elsewhere then it will almost surely pass through the atom. Therefore, P (W ∈ ∂K) = 0, so the Portmanteau Theorem applies. By the definition of K, and since γ, i were arbitrary, τ N,n N , Y N τ N,n d − → (τ n , W τ n ) as N → ∞, for any n.
Theorem 5.8. If P N is our discrete optimal value, and τ is the optimal continuous time stopping time, then P N → E [F (W τ , τ )] , as N → ∞.
Proof. We know from our choice ofF that F N (x, N t) − F (x, t) ∞ → 0 as N → ∞. Then by Lemma 5.6 and the boundedness of F , we have Also, Lemma 5.5 shows that (W τ N , τ N ) P − → (W τ ∞ , τ ∞ ) as N → ∞ and so, since F is bounded, where τ ∞ is the hitting time of a cave barrier such that W τ ∞ ∼ µ, since L (W τ ∞ ) = lim N →∞ L Y N τ N = lim N →∞ µ N = µ. Then, by the optimality of τ , combining these results gives Theorem 5.1 gives the other inequality, as mentioned in Remark 5.3.

Conclusions
Lemma 5.5 and Theorem 5.8 recover the cave embedding result proved using the monotonicity principle in [4], that is, there exists a cave barrier such that the hitting time of that barrier minimises E [ϕ(σ)] over stopping times σ such that W σ ∼ µ. In addition, these results characterise these boundaries/stopping times as the limits of solutions to a discrete problem. The equivalent results hold in the cases of the Root and Rost embeddings, and also in the case of K-cave embeddings from [11]. As well as this approach being a novel way of reproving the existence of these embeddings, it can also be used to derive properties of the continuous time problem which are not easily deduced otherwise. For example, our principal motivation for this work was to establish the form of the optimal superhedging portfolio of a European call option on a leveraged exchange traded fund, and without the work here it is not clear that such an optimal portfolio exists. In Section 3.2 we give an indication of how our dual optimisers (η * ,N , ν * ,N ) converge to functions with which we can superhedge our payoff F , and this is formalised in [11,Section 5.1]. Optimal superhedging portfolios are given for Root and Rost-type payoffs in [13] and [12] respectively, and we can also use this approach to recover those functions.
The discrete setup of this problem is robust in the sense that we can change the problem somewhat and hope to still prove strong duality and derive properties of the associated continuous time problem. By changing the conditions at t = 1 in P N we can consider the problem where our random walk starts according to some more general initial distribution. The strong duality and convergence results above will still hold provided we choose a starting measure (for the Brownian motion) µ 0 such that µ 0 ≤ µ in convex order, and choose the discretisations µ N 0 carefully. Here we consider the case where the full distribution of the process at the terminal time is known, but this approach could give more insight into the problem where the potential of the terminal distribution is only given at finitely many points.
In the financial problem of finding robust bounds on the price of some exotic option, the Skorokhod embedding problem arises as a consequence of the Breeden-Litzenberger formula of [8]. This result allows us to calculate the terminal distribution of a price process if we can observe the prices of European call options on this process at some fixed terminal time for all possible strikes. A more realistic assumption is that we can observe the call prices at finitely many strikes, and then we can only calculate the potential of the terminal distribution at these points.