{'fraction_non_alphanumeric': 0.04353034187010373, 'fraction_numerical': 0.01578783450324621, 'mean_word_length': 3.9200848656294203, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Cut-and-permute algorithm for self-avoiding walks in the presence of surfaces

We present a dynamic nonlocal hybrid Monte Carlo algorithm consisting of pivot and ``cut-and-permute'' moves. The algorithm is suitable for the study of polymers in semiconfined geometries at the ordinary transition, where the pivot algorithm exhibits quasi-ergodic problems. The dynamic properties of the proposed algorithm are studied in d = 3. The hybrid dynamics is ergodic and exhibits the same optimal critical behavior as the pivot algorithm in the bulk.


Introduction
In this paper we introduce and discuss the properties of a hybrid Monte Carlo algorithm which can be used to study the equilibrium properties of a polymer molecule grafted to a surface.
The system can be experimentally obtained either by chemically grafting one polymer end in an irreversible way, or, as for surfactants, via physical adsorption of an endgroup or one of the two blocks in a diblock copolymer. In this last case, the process is reversible, since the attached end can desorb both when the temperature increases and when the solvent quality changes.
Systems of this kind include polymers grafted at colloidal particles or surfaces in solution which can help stabilizing against flocculation [1] or polymers grafted at flexible lipid membranes exerting on the membrane a bending force which is proportional to the monomer concentration at the membrane [2][3][4][5].
In what follows we will consider a polymer in a good solvent which is grafted at a surface S and interacts repulsively with S. We will focus in particular on the case in which S is a flat surface. The polymer will be modelled by an N-step lattice self-avoiding walk (SAW), which provides a good description of the critical behavior of polymer molecules in the bulk as well as in confined geometries [6,7].
Efficient simulations of SAWs can be obtained by using nonlocal algorithms. For instance, the pivot algorithm (see Refs. [8][9][10][11] and references therein) is optimal, up to a constant factor, for sampling global observables in the fixed-N free-endpoint ensemble in the bulk since the autocorrelation time in CPU units is simply proportional to N. In the presence of surfaces, this algorithm is not as efficient and in some cases it is not even ergodic (this is the case of a two-dimensional strip, see Ref. [12]). In the presence of a single impenetrable plane, the algorithm is ergodic, but still one expects it to be inefficient since the initial part of the walk will be rarely updated. For instance, we will show that, in order to update the direction of one of the first links pointing along the normal vector to the surface, the walk should have an extremely unlikely geometrical shape. This means that, in order to explore the relevant phase space, the algorithm has to go through highly improbable configurations. Therefore, even if ergodic, the algorithm has an autocorrelation time that grows rapidly with N.
To overcome these problems, we propose here a hybrid algorithm based on the pivot move and on a cut-and-permute move. This last move has been introduced in Ref. [13] in a hybrid algorithm working in the fixed-endpoint, variable-N ensemble. It consists in cutting the walk into two parts and in rebuilding it by concatenating the two parts in the opposite order. As we will discuss, such a move is quite efficient in changing the configuration of the walk near the grafted endpoint. Thus, if we combine the pivot move and the cut-andpermute move, we obtain an algorithm which does not have the quasi-ergodicity problems of the pivot algorithm. Also, by a careful implementation, it is possible to obtain the same optimal behavior as the pivot algorithm for polymers in the bulk: the autocorrelation times of global observables in CPU units increase only as N. It must be noted that, even though we consider here only the case of a flat surface, the results should apply to any convex surface, for instance to polymers grafted outside a sphere: in this respect, the plane should be the worst case. Note also that we do not consider here any interaction between the surface and the walk other than the excluded-volume interaction. Nonetheless, the results should also hold in the presence of attractive interactions as long as they are sufficiently weak and the walk is not absorbed. In this case, it is probably important to add local moves (and, perhaps, bilocal moves as defined in Ref. [12]) to speed up the dynamics near the surface. Finally, we want to notice that this algorithm is also needed if we want to apply the join-and-cut algorithm of Ref. [14] to walks in the presence of a surface. Indeed, the ideas that are presented here apply directly to that algorithm, so that by using the cut-and-permute together with the pivot move, one should be able to have a version of the join-and-cut algorithm which works reasonably well also in the presence of a surface.
The paper is organized as follows. In Sec. 2 and 3 we consider the pivot and the cutand-permute move and discuss in detail the acceptance fraction, paying particular attention to those moves in which the pivot or the cutting point is near the grafted endpoint of the walk. In Sec. 4 we discuss the implementation of the two moves and compute the scaling behavior of the average CPU time for each move. In Sec. 5 we discuss the full algorithm, showing its optimal behavior.

The Pivot move in the presence of a surface
In this paper we will consider N-step self-avoiding walks on a d-dimensional lattice Z d in the presence of an excluded surface S of equation S( x) = 0, x ∈ Z d . A SAW ω is a sequence of lattice points {ω 0 , . . . , ω N }, such that ω i , ω i+1 are lattice neighbours and ω i = ω j for i = j. The walk is confined in the outward half-space S( x) ≥ 0 with its first vertex grafted at S and fixed at position ω 0 . The state space is therefore As probability measure on the space Ω S N (ω 0 ), we will consider the uniform one, which gives equal weight to every allowed walk, i.e. π (ω) = 1 c S N , where c S N is the cardinality of Ω S N (ω 0 ). In the following we will assume S to be a (d − 1) hyperplane of equation z = 0.
In Ω S N (ω 0 ) we will first consider the pivot algorithm [8,9]. The elementary move of the algorithm in the bulk consists of the following steps: 1. Given a walk configuration ω = {ω 0 , . . . , ω N }, an integer k ∈ {0, . . . , N − 1} is chosen at random and the corresponding monomer ω k is taken as pivot point.
2. An element g of the symmetry group of the lattice is chosen at random with probability p g and a new walk is built by applying it to the part of the chain which follows the pivot point, using ω k as fixed point of the transformation. A walk ω ′ = {ω ′ 0 , . . . , ω ′ N }, where the new monomer coordinates are given by is obtained.
3. If the walk ω ′ is not self-avoiding the move is rejected and the original walk ω is kept. Otherwise, ω ′ is taken as new current walk.
We require p g = p g −1 in order to satisfy detailed balance. In the bulk the algorithm is ergodic if all axes reflections and either all π/2 rotations or all diagonal reflections are given nonzero probability [8]. Note that in the bulk, in step 1, we can restrict k to belong to {1, . . . , N − 1}, since pivot moves with pivot ω 0 are symmetry transformations. However, this is not the case in the presence of a surface, and it is thus important to include k = 0.
A further requirement has to be satisfied in order to take into account the excluded region: . . , N, the move is rejected and the old walk is counted again.
Because of the presence of the excluded region, ergodicity is not always satisfied. If S is a (d − 1)-dimensional hyperplane, one can prove that axes reflections and π/2 rotations are enough to ensure ergodicity. However, even if ergodicity is satisfied, one may be worried by the fact that in order to explore the relevant phase space, the algorithm has to go through highly improbable configurations. For instance, if we denote byẑ the direction perpendicular to the hyperplane S, we expect the algorithm to be quite slow in updating the links at the beginning of the walk that are directed in theẑ direction. Indeed, transformations that have the pivot near the surface and that modify theẑ direction-moves involving the inversion of the z-axis, reflections with respect to the diagonals, π/2 rotations in the x = 0 or y = 0 planes-are unlikely to be accepted because of the excluded region.
Therefore, it is important to study the dynamic behaviour of the algorithm as a function of the pivot point in order to determine whether the algorithm is still efficient. For a generic move based on a lattice symmetry transformation g applied in the pivot point ω k we can define a local acceptance fraction f g,piv (N, k). In the scaling limit N → ∞, k → ∞ with k/N finite, the local acceptance fraction is expected to satisfy the scaling Ansatz where p g,piv is the exponent which asymptotically governs the decay of the global acceptance fraction for N → ∞ and h g,piv (k/N) is a scaling function. For small values of α ≡ k/N the behaviour of the scaling function h g,piv (α) depends drastically on whether or not the transformation g preserves the z coordinate of the walk. In order of analyse quantitatively the dynamic behaviour of the algorithm, we group the pivot moves into equivalence classes. Two pivot moves which are based on the symmetries g and g ′ are said to be equivalent if there exists a global symmetry σ-i.e. a transformation of the whole walk-which preserves the geometry of the system (i.e. a lattice symmetry which does not modify the z coordinates) such that, for every walk ω ∈ Ω S (ω 0 ) and for every pivot point ω k , the walk which is obtained by applying a pivot move based on g ′ to the globally σ-transformed walk σ(ω) in the pivot point ω ′ k = σ(ω k ) and then transforming back via σ −1 coincides with the walk obtained from ω by means of a pivot move based on the symmetry g with pivot point ω k . In formulae, if we denote by G k the operator associated with the pivot move based on g applied on monomer k, then g and g ′ are equivalent, if, for every k, For instance, consider the transformations g : (x, y, z) → (x, z, y) and g ′ : (x, y, z) → (x, −z, −y). It is a simple matter to show that they are equivalent: It is enough to consider the π/2 rotation σ : (x, y, z) → (x, −z, y).
In 3 dimensions the original 47 different moves are classified in 15 different classes. Moves belonging to a given class have exactly the same critical behaviour. Therefore, in the following we will study Eq. (3) for different classes of moves.
In Fig. 1 we report the acceptance fraction for the 15 classes as a function of α, for N = 100. For small α, that is for pivot points that are near the surface, there are essentially three types of behaviour. Moves that involve the inversion of the z-axis have a very low acceptance rate: for α = 0.1 the acceptance of, say, reflections with respect to the z-axis is 0.04 and it drops further to 0.0045 for α = 0.05. Transformations that involve π/2 rotations and diagonal reflections have a better behaviour although the acceptance still drops as α → 0. Transformations that do not modify the z-direction are instead unaffected by the presence of the surface.
Although the behaviour of the acceptance fraction as a function of α is radically different between SAW in the bulk and SAW in a half-space, the critical behaviour of the global acceptance fraction averaged over k is very similar.
Denoting with f i,piv (N, k) the acceptance fraction of the class of moves i applied in the pivot point ω k , and with f i,piv N its average over k, we expect f i,piv N to vanish as the length of the walk increases as where the index i indicates a symmetry class, ∆ i is the corresponding leading correctionto-scaling exponent, and A i , B i are non-universal amplitudes. Before giving a quantitative estimate of the exponents p i,piv , we try to give heuristically a rough estimate of the relative order of magnitude of the acceptance exponents in the bulk and in the presence of the surface. The argument which we use was already introduced in Ref. [8] for SAW's in the bulk and we simply extend it to the case of SAW's in a half-space.
If the two parts of the walk ω [0, k] = {ω 0 , . . . , ω k } and ω [k, N] = {ω k , . . . , ω N } are considered as independent, the local acceptance fraction for any applied lattice symmetry in the bulk would be given by where c k is the number of walks of length k. For k → ∞, where µ is the critical fugacity and γ ≈ 1.1575(5) [15], so that we have and p i,piv ≈ γ − 1 ≈ 0.16.
In the presence of the surface the same argument gives wherec k ( r) is the number of walks of length N starting from r. For k → ∞,c k (0) ∼ µ k kγ −1 , where µ is a fugacity which is identical to that appearing in Eq. (6) andγ a new critical exponent. In three dimensions,γ ≈ 0.68 [16][17][18]. Assuming ω k to be at a (macroscopically) finite distance from the surface we can takec N −k (ω k ) ∝ c N −k , where c N −k scales according to Eq. (6). Then, Eq. (8) gives again f i,piv ∼ N 1−γ , i.e. p i,piv ≈ γ − 1 ≈ 0.16. Thus, heuristically, we expect the acceptance exponents p i,piv to be of the same order in the presence of the surface and in the bulk. This is confirmed by the numerical estimates.
In order to compute the acceptance exponents p i we considered walks of length N = 100, 200, 400, 800, 4000, 8000, 16000, 32000 and performed fits of the global acceptance fraction for each class of moves to a simple power law. In order to study the effect of the subleading terms appearing in (4) we performed different fits using only data for N ≥ N min for increasing values of N min = 100, . . . , 16000. We obtained as a result the effective exponents which are reported in table 1 and which approach p i as the lower cutoff N min increases.
Except for a few cases, which in the following we indicate with a star, the results are stable for walks of length N ≥ 4000. Our best estimates for the different classes of moves are: Here we have grouped the equivalence classes in the presence of the surface in 9 groups. These groups correspond to the 9 equivalence classes for the algorithm in the bulk, where one can consider global transformations σ that do not preserve the z coordinate. From the results we observe that the exponent p piv depends only on the equivalence class in the bulk. In agreement with the above-reported heuristic argument, the presence of the surface has no influence on the acceptance exponents of the different classes of moves, but only on the shape of the scaling functions h i,piv (α) introduced in Eq. (3). On the other hand, one should observe that the acceptance exponents which correspond to different bulk equivalence classes are different, with the only exception of classes 8. and 9., which can be hardly distinguished even in the presence of the surface. One should also notice that the exponent is larger for 3-axes reflections than for diagonal reflections. As it has been already noticed in Ref. [8] this can be understood intuitively. Indeed, two subwalks on the opposite sides of a pivot point tend to be directed and occupy on average opposite regions of space. We can imagine, for instance, that the two subwalks occupy two opposite octants which touch at the pivot point. The subwalk ω [k, N] is not moved in the opposite octant by pivot moves based, for instance, on a one-axis reflection, a diagonal reflection or a π/2 rotation, while a 3-axes reflection will move the whole subwalk in the opposite octant. Therefore, it should have a higher probability of rejection.
The stability of most of the fits with N min seems to rule out the possibility that all equivalence classes have the same exponent and that the discrepancies are due to residual corrections to scaling. Different symmetries have apparently different acceptance exponents. If this is correct, the global acceptance exponent p piv averaged over all transformations would coincide with the exponent of the pivot move which, in the limit N → ∞, has the highest probability of being accepted, that is p piv ≈ 0.089. This exponent is lower than that reported in Ref. [9] which was obtained by averaging over all transformations. We mention that if we also perform the group average we obtain p piv ≈ 0.116(1). The group average exponent is only slightly higher than what can be found using the data reported in Ref. [9] for the pivot algorithm in the bulk, for which p ≈ 0.113 1 . Now we can use our best estimates of the acceptance exponents for testing our scaling Ansatz (3) and determining the behaviour of the scaling functions h i,piv (α) for α ≡ k/N → 0. We will show that for α → 0 with q i < 0 for the "good" moves which do not change the z coordinate of the walk, and q i > 0 otherwise. In Fig. 2 we report f i,piv (N, k) · (N/100) p i,piv =ĥ i,piv (α) for 4 different classes of moves: 1.(b), 3.(b), 9. and 3.(a). They are representative of the different types of behaviour for α → 0. One observes very good scaling, the data for different N falling one on top of each other, except at small values of α for those moves for whichĥ i,piv is nonzero at small α in the range of N values we have considered. Indeed, for moves 1.(b) and 3.(b) the estimates increase as N increases: for N = 100 we would estimateĥ 1.(b),piv (0) ≈ 0.92 and h 3.(b),piv (0) ≈ 0.84, while for N = 32000 we haveĥ 1.(b),piv (0) ≈ 1.12 andĥ 3.(b),piv (0) ≈ 1. 10. For the moves of class 9., instead, the curve for N = 100 is slightly higher than that for N = 4000, 32000: for N = 100 we would estimateĥ 9.,piv (0) ≈ 0.15, while for N = 4000, 32000 we would obtainĥ 9.,piv (0) ≈ 0.07, although the data for N = 32000 seem to be even lower. Clearly, for small α, there are significant corrections to scaling and indeed we will now show that h 1.(b),piv (α) and h 3.(b),piv (α) diverge for α → 0, while h 9.,piv (0) = 0.
Consider first moves in classes 1.(b) and 3.(b) and in general all the moves preserving the z-coordinate of the walks. They are only marginally affected by the presence of the surface. The only effect is that, since the surface induces a monomer depletion near the surface, a move applied in a pivot point ω k with small k has higher probability of being accepted than the same move applied in ω N −k , explaining the slight asymmetry of the scaling curves h i,piv (α). Moreover, we expect the local acceptance fraction f i,piv (N, k) to remain finite as N increases with k fixed and small. By comparing with the scaling Ansatz (3), it follows that h i,piv (α) ∼ α −p i,piv , i.e. q i = −p i,piv and the scaling function diverges for α → 0. This is confirmed by the numerical results: indeed,ĥ 1.
Let us now consider the classes of moves which change, but do not invert, the zcoordinate, for instance class 9. In order to understand the behaviour of h i,piv (α) for α → 0 we must compute the local acceptance probability for k fixed and small. For this purpose, we have considered the acceptance fraction averaged over the pivot points k ≤ k max , i.e. f 9.,piv (N, k max ) = 1 k max + 1 kmax k=0 f 9.,piv (N, k) .
For fixed k max , it decays faster than the global acceptance fraction. For instance, for k max = 20, for the moves that involve π/2 rotations or diagonal reflections in the (y, z), (z, x) planes (classes 8. and 9.), we have numerically foundf 8.,9.,,piv (N, 20) ∼ N −0.49 . It will be shown in the following that this exponent is close to the one which characterizes the probability that a generic bulk N-step SAW grafted at the surface belongs to Ω S N (ω 0 ). Since we expect that f 8.,9.,piv (N, k max ) ≈f 8.,9.,piv (N, k max ) for small k, the scaling function h 8.,9.,piv (α) is expected to vanish with q 8.,9. ≈ 0.49 − p 8.,9.,piv ≈ 0.37. Similar behaviour is expected for all classes of moves ( 2. The behavior of moves like 1.(a) that invert the z-axis is much worse. For instance, we performed a long run for N = 800, in which such moves were attempted on the first 20 monomers approximately 21000 times, and none of the attempts was successful. Fitting directlyĥ 1.(a) (α) for α = k/N ≤ 0.1 for N = 100, 800, 4000, one finds q 1.(a) = 3.8 (3).
It can be useful to get heuristically a rough idea of the order of magnitude of the exponent q 1.(a) . Let us denote with m N (ω, k) the maximum elongation in the z direction of the monomers following the pivot point where ω z i is the z-coordinate of the monomer ω i . If we denote with ω z k the z-coordinate of the pivot point, the proposed move does not give rise to collisions with the surface if the inequality is satisfied. Thus, if the pivot point is one of the first vertices following the grafted end, Eq. (12) states that the move may be successful only for those walks that have nearly all their monomers within few lattice planes from the surface and therefore we expect that h(α) vanishes for α → 0. It is known (see Ref. [6]) that for N → ∞, z → ∞ and ζ ≡ z/N ν fixed and small, the probability distribution P N (z) of the fraction of monomers which lay at a distance z from the surface scales as Therefore, the fraction W (z) of monomers that lay within a distance z from the surface scales as If k is small but already in the scaling regime, we expect that ω z k ∼ k ν and therefore W (2ω z k ) ∼ k/N = α. Therefore, since the average fraction of monomers laying in the strip z < 2ω z k is α, the average fraction of walks such that all their monomers lay in the strip is less than α. It follows that q 1.(a) ≥ 1.
Clearly, the pivot move is inefficient when the pivot is near the surface. Therefore, we expect the dynamics of observables that strongly depend on the behavior of the walk near the surface-for instance, the number of monomers on the surface-to be much slower than that of global observables. Also, note that τ exp becomes rapidly large, making it very difficult to thermalize the system using only the pivot algorithm. In the following Section we discuss a second nonlocal move that solves the problems we have discussed.

The Cut-and-permute move
In this Section we want to consider a different nonlocal move that is able to modify the walk near the surface. By adding it to the pivot algorithm we will obtain an algorithm without the quasi-ergodicity problems we have discussed above. Of course, we do not want to destroy the optimal dynamic behaviour of the pivot algorithm, and thus we want to introduce a move for which the mean CPU time per succesful move scales simply with N. The move we introduce here consists in cutting the walk in two parts, and in rebuilding the walk in reverse order.
2. Cut the walk in the cut-point and rebuild it arranging the two subwalks ω 1 and ω 2 in reverse order. The resulting walk ω ′ has vertices at positions 3. The proposed move is accepted if the resulting walk ω ′ is self-avoiding and does not intersect the excluded region.
It is easy to see that the move satisfies detailed balance as long as It is also possible to incorporate in the cut-and-permute move the "good" pivot transformations, i.e. those that do not change the z-coordinate. We thus define an "improved" cut-and-permute move as follows (the move is illustrated in Fig. 3): The point ω c divides the walk in two subwalks ω 1 = {ω 1 , . . . , ω c } and ω 2 = {ω c+1 , . . . , ω N }.
2. Choose with probability P g an element g belonging to the symmetry group of the plane which is parallel to the surface. In three dimensions the symmetry group is the dihedral group D 4 in the z = 0 plane, whose 8 elements are ±π/2 rotations, π rotation, axis inversions, diagonal reflections, and the identity.
3. Apply the chosen symmetry to the subwalk ω 2 to obtain the subwalk 4. Cut the walk in the cut-point and rebuild it arranging the two subwalks ω 1 and ω 2 ′ in reverse order. The resulting walk ω ′ has vertices at positions 5. The proposed move is accepted if the resulting walk ω ′ is self-avoiding and does not intersect the excluded region.
The improved cut-and-permute move does not satisfy detailed balance. Indeed, the walk ω ′ obtained from ω with a cut-and-permute move in the cut-point ω c cannot be transformed back to the original walk ω by any move applied in ω N −c , since the subwalk of ω following the cut-point has changed its orientation in space and its orientation cannot be modified in the second cut-and-permute move. However, the move still leaves the probability measure invariant as long as p c = p N −c . Indeed, if we perform a move based on g in the point ω c and then a move based again on g in the point ω N −c , we obtain the walk ω ′′ = g (ω) corresponding to the application of symmetry g to the original walk. If we denote by p(ω → ω ′ ) the probability that the move applied to ω gives as result ω ′ , from what we have described it follows that p(ω → ω ′ ) = p(ω ′ → g(ω)). Thus, as required. In the following we will consider the improved cut-and-permute move, but, as we shall show explicitly, nothing would change by using the simpler version. As it has been done for the pivot algorithm, we can define equivalence classes of cut-andpermute moves and study the acceptance fraction f i,cp (N, c) as a function of the position c of the cut-point and its average f i,cp N over all points c. For large N, we expect a scaling behavior of the form We have not added an index i to p cp because, as we shall see, this exponent does not depend on the equivalence class.
To give an estimate of the exponent p cp , we can use again a heuristic argument in which we consider the two subwalks in which the original walk ω is divided at the cut-point ω c as independent. We also assume that the probability that the attempted move is accepted is the product of the probability P 1 (c) that the concatenation of the two subwalks gives a walk which does not have self-collisions times the probability P 2 (c) that the subwalk ω 2 , transformed under a D 4 symmetry and translated with its first vertex on the surface does not intersect the forbidden region. Repeating the argument presented for the pivot case, we have which, by averaging over c, gives P 1 ∼ N −(γ−1) ∼ N −0.1575 (5) . The second probability is given by which, after averaging, gives P 2 ∼ N −(γ−γ) ∼ N −0.48 . The global acceptance fraction of the cut-and-permute move is expected to scale as f cp = P 1 · P 2 ∼ N −pcp ∼ N −2γ+1+γ ∼ N −0.63 . This argument is likely to give an overestimate of the exponent p cp for the following reasons. The original subwalk ω 1 which is grafted at the surface is directed, so that P 1 (c) is underestimated. Moreover, the walk ω 2 is expected to have a residual directionality in the +ẑ direction so that the probability that ω 2 does not intersect the forbidden region is expected to be larger than P 2 (c). Table 2 contains numerical estimates of the acceptances f cp,i N for different classes of moves in D 4 at different values of N, averaged over the cutting point c. We have fitted the data for N ≥ N min to a power law considering increasing values of N min . Systematic errors due to corrections to scaling should become negligible for N min → ∞. The χ 2 values of fits with N min ≥ 4000 indicate that the fits are stable, with the exception of two cases. These two cases are denoted with a star in the following list containing our best estimates for the exponent p cp : At variance with the pivot case the results for the different equivalence classes are compatible within error bars: the transformation g seems to play little role. If we average over all symmetries we obtain p cp = 0.4922(20). Note that, as expected, this result is somewhat lower than the heuristic estimate reported above.
The exponent p cp is significantly higher than p piv so that cut-and-permute moves will be more rarely accepted. Numerically, we find that a cut-and-permute move is accepted every ∼ 2 (resp. ∼ 20) succesful pivot moves for N = 100 (resp. N = 32000). However, they represent the moves that most effectively change the conformation of the walk near the grafted end and thus they will play an important role in decorrelating the walk configurations.
As for the pivot case, it is interesting to study the local acceptance fraction as a function of c and N. For N → ∞, ζ ≡ c/N fixed we expect a scaling form where h cp (ζ) is a scaling function which encodes the dependence on the different cut-points.
In Figure 4 we report the functionĥ cp (ζ) = f cp (N, c) · (N/100) pcp for 5 values of N using the exponent p cp given by our fits. There is no difference in the local behaviour of the 5 classes of equivalent moves, so the function we report refers to the total acceptance obtained by averaging over the equivalence classes.  (N, N − c), to conclude the argument. In conclusion, the cut-and-permute move has a good scaling behavior exactly in the region in which the pivot moves behave badly. The addition of the cut-and-permute move in the hybrid dynamics is therefore crucial in speeding up the dynamics of the first steps of the walk. As in the pivot case, since the local acceptance fraction converges to a constant for small or large fixed values of ζ, the scaling function h cp (ζ) increases as ζ −pcp for ζ → 0 (resp. (1 − ζ) −pcp for ζ → 1.) This suggests that in step 1. one can take p c different from 0 only for ζ near 0 and 1, i.e. set p c = 0 if αN ≤ c ≤ N(1 − α). For instance, by taking α = 1/10, we would approximately increase the acceptance by a factor 1.7.

Computational complexity
In order to study the effective dynamic behaviour of the algorithm in CPU time, it is important to determine the scaling behaviour of the CPU time needed to generate pivot and cut-and-permute successful moves.
The CPU time depends on the data structure that is used. For the walk we consider a sequentially allocated linear list and in order to check for self-collisions and collisions with the surface we use a hash table as described in Ref. [8]. This allows to insert a single monomer in an average CPU time of order one. In the following we will define a CPU time unit as the CPU time which is needed to upgrade a single monomer position.
In order to optimize the algorithm, it is important to mimimize the CPU time spent in a failed attempt. This requires a careful choice of the order in which the new walk ω ′ is rebuilt.
For the pivot algorithm, Ref. [8] suggested to build the new walk and perform the selfavoidance check in the following order: . . till all monomers have been checked. The motivation was that the probability of self-intersections is higher for those monomers which are close to the pivot point. However, in the presence of a surface a move that changes the z-coordinate can also fail because the new walk intersects the surface.
Intersections with the surface occur with higher probability for those monomers of the subwalk ω [k, N] which are more likely to undergo a large displacement, while monomers belonging to the grafted subwalk ω [0, k] are not modified and satisfy the geometrical constraint automatically. In order to keep into account this effect, for the moves that change the z-coordinates, we can use a different strategy: we insert the monomers of the proposed walk ω ′ in the hash table in the following order: till every monomer has been checked once. As a measure of the CPU time spent by the algorithm we can use the number of walk monomers I(ω ′ ) that are checked in the move. If the move is successful, clearly I(ω ′ ) = N, while for a failed attempt where, following Ref. [8], we denote the subwalk {ω ′ max(i,0) , ω ′ max(i,0)+1 , · · · ω ′ min(j,N ) }, with the symbol ω ′ [i, j] and the half-space z < 0 with • S. We want now to evaluate the average time spent in checking a failed move that is expected to scale as where the average over all failed moves is taken. An estimate of y piv can be obtained by a heuristic argument. Inserting monomers in the hash table in the way we described before, the probability that I(ω ′ ) exceeds the value i can be estimated from the scaling of the acceptance fraction. Indeed, we expect Therefore, the average time spent in checking a failed move is expected to scale like so that y piv = 1 − p piv . Estimates of T piv,f ailed N are reported in Table 3, for the different classes of pivot moves and different values of N. We performed fits of the form (24) in order to determine y piv , including each time only data with N ≥ N min (in Table 3, N min is the value N reported in the first column). We observed that in all cases y piv increases with N min and thus our results are probably a lower estimate of y piv . Here, we report the results with N min = 4000 and indicate with a star those cases in which the χ 2 is still too large: 1. z-axis inversion: y piv = 0.8750 (16), x or y-axis inversion: y piv = 0.8234 (17)  If we average over all equivalence classes we obtain y piv = 0.8428 (13). These results should not be trusted too much, and in many cases the correct estimate is probably higher. However, the important thing that emerges is that y piv ∼ < 1 − p piv , a result that will be used below.
We also computed T piv,f ailed N for the moves that change the z-coordinate when we insert the points as proposed in Ref. [8], i.e. without modifying the order in which we insert monomers into the hash table because of the presence of the surface. We found that, by using this method, the average number of points inserted in the hash table before detecting a failure is approximately 1.4 times larger. The difference is more significant for pivot points ω k with k < N/2-for k/N → 0 the difference is a factor of two-while for k ∼ > 0.6 the two methods are equivalent. However, this has no influence on the exponent y piv , which is approximately the same in both cases.
At this point we can estimate the average CPU time spent in a pivot move. Clearly where we have taken into account that y piv ∼ < 1 − p piv . Notice also that more time is spent in a successful move than in an unsuccesful one.
Let us now consider the cut-and-permute move. As in the previous case we tried to build the new walk in the most efficient way in order to reduce the CPU time necessary to detect a failure. Unlike the pivot case, for the cut-and-permute move the heuristic argument indicates that the dominant cause of failure is given by intersections with the surface. As it is illustrated in Fig. 3, the cut-point ω c divides the walk in two subwalks, ω [0, c], which is grafted at the surface, and ω [c, N]. The move transforms ω [c, N] via a lattice symmetry g which preserves z and translates the transformed subwalk grafting its first vertex at the surface. The subwalk ω[0, c] is instead translated in order to join the free end of the grafted subwalk. The only possibility of hitting the surface comes from the new grafted subwalk ω ′ [0, N − c] and the monomers which are more likely to intersect the forbidden region are the ones following the new grafted vertex. Collision between monomers are instead more likely to occur at the joining of the two subwalks.
As for the pivot move, in order to check at the same time the two regions where failures are more likely to occur, we inserted the monomers of the proposed new walk ω ′ in the hash table in the following order: In this way the CPU time needed to check a proposed walk is if ω ′ is rejected and I(ω ′ ) = N if it is accepted. The average time spent in detecting a failed move is expected to scale as We can estimate y cp heuristically as before. With the above procedure the probability of using CPU time which is longer than i goes as and the average total time spent in a failure scales as so that y cp = 1 − p cp . The data for T cp,f ailed N in the cut-and-permute move and the estimates of the y cp exponent obtained from data with N ≤ N min , with N min appearing in the first column, are reported in Table 4. From those data we have computed our final estimates as we did in the pivot case obtaining: The group average y cp = 0.4890(15) is slightly lower than 1 − p cp ≈ 0.5078(20) as it is also happened for the pivot move.
In order to confirm the role played by intersections with the surface, we also measured I(ω ′ ) when monomers are inserted in the hash table in the order ω ′ N −c , ω ′ N −c+1 , ω ′ N −c−1 , · · ·, without inserting at the same time the monomers near the grafted end. In this case we find y cp ≈ 0.9 which is very similar to the exponent for the pivot move. The proposed procedure is thus very inefficient.
Finally, we can estimate the average CPU time spent in a cut-and-permute move. Clearly where we have taken into account y cp ∼ < 1 − p cp . Note also that T N,cp /T N,piv ∼ N pcp−p piv ∼ N −0.4 , so that the average CPU time for successful move scales identically.

The hybrid cut-and-permute algorithm: autocorrelation times
In this Section we want finally to define our hybrid algorithm that consists in performing both pivot and cut-and-permute moves. More precisely, the algorithm is specified by a number 0 < q < 1. The hybrid algorithm works by performing a pivot move with probability q and a cut-and-permute move with probability (1 − q). Since the pivot alone is ergodic, the full algorithm is ergodic. In order to understand the dynamic behavior we will distinguish three different classes of observables: (a) global observables that depend on the global shape of the SAW, for instance, the end-to-end distance or the radius of gyration; (b) global surface observables that depend on the interaction of the SAW with the surface, for example, the number of monomers lying on S; (c) local observables that depend on local properties of the SAW.
Let us analyse at first the behaviour of global observables. Both pivot and cut-andpermute are nonlocal moves and can decorrelate global observables in few accepted moves, but the cut-and-permute move cannot modify a class of observables, for instance the zcoordinate of the free endpoint. We denote with O z the class of observables which are updated only in the pivot dynamics and with O x,y all the others. For a polymer of length N the autocorrelation time τ int,Oz is therefore of order 1/(q · f N,piv ), while τ int,Ox,y is of order 1/f N,max , where f N,max = max{q · f N,piv , (1 − q) · f N,cp }. Since in the limit N → ∞ the acceptance fraction of the cut-and-permute move decreases faster than the acceptance fraction of the pivot move, if q is constant, the scaling behaviour of the autocorrelation time τ int,glob of any global observable is determined by the pivot dynamics only, i.e.
so that z glob ≈ p piv ≈ 0.10. Table 5 reports the autocorrelation times for different values of N for the z component of the free endpoint obtained setting q = 1/2. The dynamic exponent z, which is obtained by fitting the data to a power law, is z ≈ 0.15, in reasonable agreement with the prediction. Global surface observables will be changed in a few successful cut-and-permute moves and thus we expect so that z surf ≈ p cp ≈ 0.49. Unfortunately, we have not measured surface quantities in our simulation and therefore we are not able to test this prediction. Nonetheless, we believe that the correct value of z is not too far from p cp . Finally, let us consider a local observable, for instance the average number of monomers at which the SAW makes a 90 o turn. Such a quantity is of order N with a variance of order √ N . By using a standard random-walk argument we obtain since p cp < p piv . Since local moves should be the slowest ones we expect τ exp ∼ > N 1.1 . Finally, we estimate the behaviour of the autocorrelation time for global observables in CPU units. Since the average CPU time spent in performing one move of the cut-andpermute algorithm is proportional to the autocorrelation time of global observables in CPU units scales as where, in the absence of a numerical estimate, we have used our heuristic estimate, z surf ≈ p cp . The behavior of global observables is nearly optimal, while for surface observables the behavior is not as good. If one is interested in computing surface observables, it is possible to improve the algorithm by increasing the frequency of the cut-and-permute moves. Indeed, if we scale q −1 ∼ N pcp−p piv -essentially we keep the relative frequency of successful pivot and cut-and-permute moves constant-then our previous arguments give The time per move scales now as N 1−pcp , so that In this case, the dynamics is optimal for both types of observables. Note that one cannot obtain the same result using the pure pivot algorithm. Indeed, the autocorrelation time for global surface observables would be proportional to the number of attempts occurring between two accepted pivot moves changing the z-coordinate of the walk and applied in a pivot point ω k with k small. Because of the monomer depletion near the surface, indeed, one does not expect that a move at a pivot point far from the grafted end would affect macroscopically the number of monomers near the surface. In Sec.2 we have shown that among the z-changing moves only the ones which do not invert z have a small probability of being accepted for small k. This probability decays as N −x with x ≈ p cp ≈ 0.49. Therefore, if we choose the pivot point with uniform probability, we get and the autocorrelation time in CPU units scales as This indicates clearely that the pivot algorithm alone is inefficient for simulating polymers grafted at an inpenetrable interface.      N τ z end N ± δτ z end N z ± δz χ 2 DF 4000 10.347 ± 0.040 0.1506 ± 0.0029 1.564 2 8000 11.420 ± 0.037 0.1543 ± 0.0041 0.007 1 16000 12.703 ± 0.087 0.155 ± 0.012 0.000 0 32000 14.146 ± 0.068 Table 5: Autocorrelation times and dynamic exponent z glob for the observable z end .