## Improved Randomized Rounding using Random Walks

Sandeep Sen Department of CSE, I.I.T. Delhi, India ssen@cse.iitd.ernet.in

August 5, 2014

## Abstract

We describe a novel algorithm for rounding packing integer programs based on multidimensional Brownian motion in R n . Starting from an optimal fractional feasible solution ¯ x , the procedure converges in polynomial time to a distribution over (possibly infeasible) point set P ⊂ { 0 1 , } n such that the expected value of any linear objective function over P equals the value at ¯ x . For n O (1) packing constraints in n variables, the constraints are satisfied within O ( √ log n ) . This improves the O ( log n log log n ) error incurred by the classical randomized rounding method of Raghavan and Thompson [RT87].

Our procedure is very general and in conjunction with discrepancy based arguments, yield efficient alternate methods for rounding other optimization problems that can be expressed as packing ILPs including disjoint path problems and MISR.

## 1 Introduction

Many combinatorial optimization problems can be modeled using a weighted (non-negative) packing integer program subject to

$$\text{Maximize } \sum _ { i = 1 } ^ { i = n } c _ { i } \cdot x _ { i }$$

$$\sum _ { i \in S _ { j } } x _ { i } & \leq 1 \ 1 \leq j \leq m \ \ x _ { i } \in \{ 0, 1 \} \\ \dots \colon \colon \colon \dots \dots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots$$

where wlog, we can assume that max i c i = 1 . Although the above formulation appears somewhat restrictive having a fixed right hand side of each inequality, the methods that we develop can be extended to the general case. Often the constraints are expressed as C j : V j · ¯ x ≤ 1 where V j is a 0-1 incidence vector corresponding to set S j ⊂ { 1 2 , . . . n } . Since this version is also NP-hard as it captures many intractable independent set problems, a common strategy is to solve the Linear Program (LP) corresponding to the relaxation 0 ≤ x i ≤ 1 . Then use the LP optimum L o to obtain a good approximation of the optimal integral solution. Suppose the optimum is achieved by the vector ¯ x ′ = [ x , x ′ 1 ′ 2 . . . x ′ n ] In the conventional randomized rounding [RT87], we round each x ′ i independently in the following manner.

$$\text{name}.$$

It can be easily shown that E [ ∑ i c x i ˜ ] = i ∑ i c i · x ′ i and for all j , w.h.p. ∑ i ∈ S j ˜ x i ≤ ( log n log log n ) . The primary application of improved randomized rounding is improved approximation of integer linear packing problems. Historically, the original randomized rounding technique was proposed for

obtaining better approximation of multicommodity flows [RT87] and it was established much later [CGKT07] that the bound of log n log log n for the congestion minimization is tight upto constant factors under the separation assumption of complexity classes BPP and NP . In light of this, one may be tempted to conjecture that the rounding bound given by Raghavan and Thompson is tight. However, the way the rounding was applied to this problem was not independent rounding but involved a k -sided coin toss that guarantees exactly one success among a set of random variables. Srinivasan [Sri95, Sri99] presents an extensive survey of many sophisticated variations of randomized rounding techniques and applications to approximation algorithms.

In order to decrease the error for each inequality after rounding we propose an alternate approach based on a constrained multidimensional random walk - more specifically based on Brownian motion. As opposed to the one-shot rounding of [RT87] , hitherto referred as oblivious rounding , our rounding is iterative and based on successive refinements of the LP solution that has a lower variance per step, seemingly related to the discrepancy.

## 1.1 Main result

We prove the following general result

Theorem 1.1 Let A ∈ { 0 1 , } m n × , b = 1 m and m = n O (1) . For any point ¯ x ′ = ( x , x ′ 1 ′ 2 . . . x ′ n ) , 0 ≤ x ′ i ≤ 1 such that A · ¯ x ′ ≤ b , there is a polynomial time randomized algorithm that rounds ¯ x ′ to a random ˆ x ∈ { 0 1 , } n such that

$$1 \leq i \leq m, A _ { i } \cdot \hat { x } \leq O ( f ( n ) \text{ where } f ( n ) = O ( \log ^ { 1 / 2 } n )$$

and for all ¯ = ( c c 1 , c 2 ..c n ) c i ≥ 0

$$\mathbb { E } [ < c ^ { T }, \hat { x } > ] = < \bar { c } ^ { T }, \bar { x ^ { \prime } } >$$

Alternately, for some constant C &gt; 1 , &lt;c T ,x&gt; ˆ &lt;c ¯ T ,x &gt; ¯ ′ ≥ 1 C .

Remark: The constant approximation factor follows from a simple application of Chebychev inequality and assuming that &lt; c ¯ T , x ¯ ′ &gt; ≥ C .

Remark It may be worthwhile mentioning that the method of Raghavan and Thompson [RT87] and subsequent refinements by Srinivasan [Sri95] could be derandomized in polynomial time. However, derandomizing our algorithm can be more challenging.

## 1.2 Prior work related to iterative rounding

Bansal's [Ban10] seminal paper on a constructive proof of Spencer's discrepancy theorem is based on rounding solutions of successive a semi-definite program that captures the discrepancy constraints. This method was further refined and simplified in the work of Lovette and Meka[LM12] who derived an alternate proof based on a very elegant analysis of a multidimensional random walk. The crux of the method called partial coloring lemma is a rounding strategy of an arbitrary x ∈ -[ 1 +1] , n vector within the discrepancy polytope defined by the constraints starting with x = (0 0 , , . . . 0) . It is done over logarithmic phases where in every phase approximately half the coordinates converge to {-1 +1 , } (actually arbitrarily close to {-1 +1 , } ) - this aspect is similar to Bansal [Ban10]. Their method can be mapped to { 0 1 , } rounding as well, that was observed by Rothvoss[Rot13]. For completeness, we state the version given in that paper.

Lemma 1.1 ([Rot13, LM12]) Let x ∈ [0 , 1] n be a starting point , δ &gt; 0 be an arbitrary error parameter and ν , ν 1 2 . . . ν m ∈ Q n be n -dimensional vectors. Let λ , λ 1 2 . . . λ m ≥ 0 be parameters such

that

Then there is a randomized algorithm with expected running time O ( ( m n + ) 3 δ 2 log( nm δ )) to compute y ∈ [0 , 1] n such that

$$\sum _ { i = 1 } ^ { m } e ^ { - \lambda _ { i } ^ { 2 } / 1 6 } \leq \frac { n } { 1 6 } \\ \dots \quad. \ \.$$

- · y i ∈ [0 , δ ] ∪ [1 -δ, 1] for at least half the indices i ∈ { 1 2 , . . . n }
- · ∀ j ∈ { 1 2 , , . . . m } | &lt; ν , x i -y &gt; | ≤ λ i · || ν i || 2

For many applications including Lovette-Meka[LM12], ν i are 0-1 incidence vectors - unless stated otherwise. If every vector is normalized, || ν i || 2 = 1 , then we can obtain bound λ i by O ( √ log( m/n ) - this version was followed in [LM12].

This implies a straightforward rounding strategy for a fractional relaxation of a linear integer program, viz., starting from the LP optimal solution ¯ x ′ , we can apply the above method successively over a logarithmic number of phases to obtain y , y 1 2 . . . y log n such that y i has n 2 log n -i coordinates ∈ [0 , δ ] ∪ [1 -δ, 1] . In the end, one application of oblivious rounding yields { 0 1 , } coordinates and this error can be controlled by the choice of δ (see Lovette-Meka[LM12] and the intermediate errors will depend on the choice of λ i according to the conditions of the previous Lemma. In the original paper, λ i = 8 √ log( m/n ) , so the error in phase i can be bounded by O n ( 1 2 / i · √ log( m/n )) , where the first term captures the two-norm in the i -th iteration. While this was ideal for the discrepancy problem, this is far from acceptable for applications related to approximation algorithms. Moreover, one needs to also account for the deviation of the objective function which was non-existent for the discrepancy problem.

Rothvoss adapted the method for the case of Karmarkar and Karp's bin-packing algorithm very cleverly by applying the LM incrementally to a subset of the items 1 and choosing λ i = 0 to control the error.

## 2 A Rounding procedure using random walks

Our approach is simple - starting from ¯ x ′ , for each variable (dimension), we will roughly 2 increment x i by ± γ for a suitably chosen 1 &gt; γ &gt; 0 where the sign (direction) is a random variable with equally probability, i.e., 1/2. In each iteration, the values of x i are modified and we continue this process for each x i until it is in the range [0 , δ ] ∪ [1 -δ, 1] for an appropriate 1 &gt; δ &gt; 0 . It should be clear that γ = o δ ( ) -the actual values will be determined in the analysis. At this point we fix the variable and we terminate when all the variables are fixed. Let the terminating vector be ˆ = [ ˆ x x , x 1 ˆ 2 , . . . x ˆ ] n . We now apply the oblivious rounding to ˆ x and output the rounded vector R (ˆ) x as the final 0-1 solution vector. The formal algorithm is described in Figure 2. The value of T will be determined in the analysis. The above algorithm doesn't take into account any of the constraints V j · ¯ x ≤ 1 and therefore likely to violate them depending on the number of steps T . It is known that for such a random walk, the probability that an x i reaches 1 before it reaches 0 is equal to the ratio x /γ ′ i 1 -x ′ i + x /γ ′ i = x ′ i . This follows from a general result that any random walk starting from origin and having two absorbing barriers at a and -b will be absorbed at a (as opposed to reaching -b ) with probability a a + b . This is a consequence of a more general property of martingales known as Doob's optional stopping theorem ([Ros06, MU05]).

1 the challenge in his case was to run it in a very high dimensional space

2 each step of the Brownian motion is actually a multidimensional normal Gaussian increment

## Algorithm Iterative Randomized Rounding

- Input : x ′ i 1 ≤ i ≤ n satisfying (LP) Output : ˆ x i ∈ { 0 1 , } Initialize all variables as un-fixed and set X 0 = [ x , x ′ 1 ′ 2 , . . . x ′ n ] = ¯ x . Repeat for iterations i = 1 2 , . . . 1. Generate a random vector R i = U i where U i is multidimensional standard Normal distribution. 2. X i +1 = X i + γ · R i . 3. Fix a variable if it is less than δ or greater than 1 -δ . If all variables are fixed then exit. { * multiple variables may get fixed in a single iteration. * } until stopping condition S Set the unfixed variables to 1 and denote this vector by ˆ x . Return the rounded vector R (ˆ) x .

Figure 1: An iterative randomized rounding algorithm based on random walks

Theorem 2.1 Let (Ω Σ , , P ) be a probability space and { F i } be a filtration of Ω , and X = { X i } a martingale with respect to { F i } . Let T be a stopping time such that ∀ ω ∈ Ω , ∀ i, | X ω i ( ) | &lt; K for some positive integer K , and T is almost surely bounded. Then E [ X T ] = E [ X 0 ] .

In the above algorithm, if we allow S to be large (allowing log n γ 2 iterations) such that all variables are fixed, the stopping times are X T = {-b, a } whichever is earlier. So - · b Pr[ X = -b ] + a Pr[ X = a ] = 0 · Pr[ X = 0] . Since Pr[ X = -b ] + Pr[ X = a ] = 1 from the stopping criteria, Pr[ X = a ] = b a + b . In our context, we start from X = x ′ i and b = x ′ i γ and a = 1 -x ′ i γ , so the probability that ˆ x i = 1 equals x /γ ′ i (1 -x ′ i + x ′ i ) /γ = x ′ i . Therefore, in this limiting case, the basic approach is similar to the oblivious randomized rounding and similar bounds can be proved. Note that the optional stopping theorem doesn't require that the step sizes are identical for all i 's and this generalization will be invoked at a later stage.

In our analysis, we will determine how to choose an appropriate stopping criterion S , that allows us to prove bounds that are superior to the conventional randomized rounding. For the curious reader, the expected number of iterations T ∗ when this happens is about 1 √ log nγ 2 . So alternately, we can run the algorithm for T ∗ iterations and accept if S is satisfied. This is better for efficiency as we do not have to check the condition in every iteration. Running it for T ∗ iteration may give a (deceptive) impression that our rounding process is equivalent to independent rounding but clearly it is not, since T ∗ is related to S .

## 3 Useful concentration bounds for Brownian motion

Although there exists a wealth of literature on Brownian motion [Fel68, Ros06], they may not be presented in the specific forms in which we invoke them for analyzing our algorithm. For the convenience of the reader, we summarize them here and refer the reader to the appendix for proofs.

The random walks that we refer to in this paper are Brownian motions in n dimensions where every step is an independent random variable chosen from a multidimensional Gaussian distribution. Each dimension is chosen independently from a standard normal distribution N (0 1) , .

Lemma 3.1 Suppose there are k independent, synchronized Gaussian random walks with absorbing barriers at {-r, + r } that started at the origin. Then with probability exceeding 1 -1 m , all the walks would have terminated within O r ( 2 log m ) steps.

Note Synchronized implies that the steps are in tandem, although independent. In some situations, it suffices that a large fraction of the walks terminates, that can be achieved in fewer steps.

Lemma 3.2 Consider k ≤ log n random walks starting from position a in an interval [0 , a + ] b where (wlog) a &lt; b with absorbing barriers at both end-points. Then for any c &lt; 1 , at least ck/ 2 random walks will be absorbed at 0 within O a ( 2 ( log n k +1) steps with probability ≥ 1 -1 n 2 .

A more accurate estimate for the fraction of walks absorbed at 0 can be obtained from the gambler's ruin problem where the underlying martingale is the Brownian motion.

Lemma 3.3 Consider a random walk starting from position a in an interval of length a + b with absorbing barriers at both end-points. Then the expected number of steps for the walk to get absorbed (at any of the ends) is a · b . Moreover, the probability of the random walk being absorbed at 0 is b a + b -2 /k after k · a · b steps for any k &gt; 1 .

Remark By choosing b &gt; k · a , the probability can be made arbitrarily close to 1 for k /greatermuch 1 -conversely, the probability of non-absorption at 0 is O ( 1 k ) after k a 2 2 steps.

## 3.1 Martingale inequalities

The successive Brownian motion steps (defined by multidimensional normal Gaussian) form a martingale sequence - the expectation is 0. The following result forms the crux of our analysis - see [Ban10, LM12] for more details and proof.

Observation 3.1 In iteration t , let Y t = &lt; V ,U j t · γ &gt; , that is the measure of the change in &lt; V , x &gt; j ¯ in the step t . Then Y t is a Gaussian random variable with mean 0 and variance γ · || V j || 2 2 .

Let V ′ j = 1 || V j || 2 V j i.e.,normalized, then the scaled random variable Y ′ t = 1 γ || V j || 2 · Y t is a Gaussian with mean 0 and variance 1. This may be preferred sometimes as tail bound on martingale sequence with standard Gaussian steps is more compact. When Y ′ i correspond to standard Gaussian, then

Lemma 3.4 For any β &gt; 0

$$\Pr [ | Y _ { 1 } ^ { \prime } + Y _ { 2 } ^ { \prime } \dots Y _ { T } ^ { \prime } | > \beta ^ { \prime } ] \leq 2 \exp ( - \beta ^ { \prime 2 } / 2 T ).$$

Moreover, it also implies that

$$\Pr [ | Y _ { 1 } + Y _ { 2 } \dots Y _ { T } | > \beta ^ { \prime } \cdot \gamma \cdot | | V _ { j } | | _ { 2 } ] \leq 2 \exp ( - \beta ^ { \prime 2 } / 2 T ).$$

(otherwise the previous inequality must have failed)

## 4 Analysis

We will divide the analysis into two components - one for the increments in the variables during each iteration that causes an inequality to be violated. Second, in the last rounding (after the end of the main iterative phase), what is the error that may cause further deviations in the variables and equation.

For convenience of understanding, let us consider a sequence of scaled polytopes P i where P 0 is the initial polytope corresponding to the feasible region and the subsequent polytopes large enough

to keep the random walk sequence X i within the polytope P i . A scaled polytope P i is the feasible region corresponding to A · ¯ x ≤ b i where b 0 = 1 m and b , i i &gt; 0 is the column vector (∆ + 1) i · b 0 , and ∆ i &gt; 0 . Instead of associating a scaled polytope for every step, we will club them into phases , where within a phase, ∆ i remains unchanged, or equivalently, we consider the cumulative effect of a number of random walk steps within the phase.

Let T , T 1 2 , . . . T i denote the number of iterations in phase i such that T = ∑ i T i . Let ∆ i 's be the accumulated error within phase i where ∆ i is some increasing function of the number of random walk steps in a phase i . Clearly, ∆ i will also depend on γ , the scaled size of a random walk step. Intuitively, with additional random walk steps, we are more likely to violate the constraints. Since the (hypothetical) constraints corresponding to the scaled polytopes are changing with time, we will denote the j -th constraint in phase t by

C t j : &lt; V , X j t &gt; ≤ 1 + ∆ t that has many of variables fixed .

Let G d i | denote the projection of the d dimensional Gaussian random variable on the coordinate x i which is the normal distribution denoted by N ( µ, σ 2 ) where µ is the mean and σ 2 is the variance. Unless otherwise stated, we will refer to the standard normal distribution where µ = 0 and σ 2 = 1 . Recall that, in the rounding algorithm X t denotes the random walk vector after t steps. Along any dimension 1 ≤ i ≤ n , let ( X t ) i denote the value of the i -th coordinate after t iterations. So ( X t ) i = W 1 + W ... W 2 t where W j corresponds to a one dimensional normally distributed random variable. Therefore ( X t ) i also has a normal distribution with mean 0 and variance t .

The success of the rounding algorithm depends on the race between the hitting of constraints C t j and the unfixed variables of V t j . In particular, we would like to hit the variable (hyper)-planes x i = 1 or x i = 0 more often than the hyperplanes C t j . The sooner the ( X t ) i hits the boundaries 0 or 1, the smaller is the displacement || X t || 2 in R n . Lovette and Meka [LM12] also make use of this observation implicitly and in their case, the discrepancy hyperplanes are much further compared to the variable hyperplanes. In our case, the situation is much tighter and much of our technical analysis revolves around that. If there are r 2 unfixed variables (a subspace with dimension r 2 ) then the variance of the displacement in each step is proportional to the L 2 norm of V j which is r . Since the sum of the r 2 variables is bounded by 1 in any feasible LP solution, at least r 2 / 2 variables have LP values bounded by x ′ i ≤ 2 r 2 which is the starting point of the random walk, ( X 0 ) i . The 1-dimensional projection is also a brownian walk ( X t ) i where each step is scaled by γ , and consequently, the r 2 / 2 variables are within 2 γ r · 2 from 0. Using a simplied argument based on number of γ -length step sizes, one needs to move ∆ rγ steps towards some constraint C j with slack ∆ versus 2 γ r · 2 steps to hit 0s of variables associated with C j . Clearly the latter is closer if ∆ &gt; 2 r . This bias in favor of hitting the variables holds the key to the success and efficiency of our algorithm and we need to capitalize on this by choosing T p appropriately, so that the many variables become fixed at 0 before X p hits the constraints (of the scaled polytope). This in turn slows down the Brownian motion further, as the norm reduces and we keep repeating this process.

## 4.1 Some useful notations

Recall that after t iterations, the j -th constraint is denoted by C t j : &lt; V , X j t &gt; ≤ 1 + ∆ t that has many of variables fixed . Suppose we denote the set of unfixed variables by U ⊂ { 1 2 , . . . n } 3 and the corresponding vector by X U t , then | &lt; V , X j t -X t +1 &gt; | = | &lt; V , X j U t -X U t +1 &gt; | as the remaining variables do not change. Let V ′ j denotes the normalized version of the vector V j . Then we can rewrite the above as

$$\underline { | < V _ { j }, X _ { t } - X _ { t + 1 } } > | = | < V _ { j } ^ { \prime }, X _ { t } ^ { U } - X _ { t + 1 } ^ { U } > | \cdot | | V _ { j } | | _ { 2 } }$$

3 Strictly speaking U is a function of t but this will be clear from the context

Although V j (correspondingly V ′ j ) are not changing the effective V j depends on U -the fewer the unfixed variables are, the less is its effect. Henceforth, we shall use V t j to denote the effective V j where only the coefficients corresponding to U are non-zero - it is the projection of V j on U . In terms of the above notation, the following is obvious

## Observation 4.1

$$| | V _ { j } ^ { \prime p + 1 } | | _ { 2 } \leq | | V _ { j } ^ { \prime p } | | _ { 2 }$$

We will classify the m inequalities in n variables into i ≤ log n buckets B i where B i = { | j 2 i -1 ≤ &lt; V , j 1 n &gt; ≤ 2 i - } 1 . Wlog, we assume that all constraints have at least 2 variables and at most n -1 variables 4 In other words, the L 2 norm of any constraint in B i is between √ 2 i -1 and √ 2 i -1 . Let B t ( j ) denote the bucket of V t j after t phases since one or more variables may get fixed and therefore the corresponding coefficients do not matter. Clearly B t +1 ( j ) ≤ B t ( j ) . i.e., the bucket number cannot increase.

## 4.2 Bounding number of unfixed variables

Suppose we have all the variables, in an inequality, say n of them starting from 1 n - these sum to 1. Let us analyze how many variables are not absorbed after T steps. We can use Lemma 3.3 to get a bound on the probability of absorption.

Claim 1 After O ( m 2 n γ 2 2 ) Brownian motion steps, the probability of absorption at 0 is ≥ 1 -1 m . For γ = 1 /n , the number of steps is O m ( 2 ) .

Proof: Given the starting position a = 1 /n 5 , let b = m a · , then we can use the result of Lemma 3.3 with k = m . So after m a/γ 2 ( ) · b/γ = m a /γ 2 2 2 steps, the probability of non absorption at 0 is O (1 /m ) . /Box

Therefore the expected number of variables that are not absorbed at 0 is bounded by O ( n m ) which is Ω(log n ) for m ≤ n/ log n . Since each of the variable is executing the random walk independently of the others, we can apply Chernoff bound to claim that the number of unfixed variables is O ( n m ) with inverse polynomial probability for m ≤ n/ c ( log n ) for a sufficiently large constant c &gt; 1 .

Let us now argue that this case ( n variables each with starting value a = 1 n ) represents the worst case in terms of rate of absorption. If there were variables with larger starting positions, then there will be fewer variables since they add up to at most 1. To simplify, let us assume that the a i 's are of the form 2 k /n for some integer k - this increases the sum of variables at most by a factor of 2. For m = 2 p , we will consider points with a i ≤ 2 p /n and note that there are at most n/ 2 p such points. Consider starting points 2 i i /n, 2 i 2 /n... 2 i j /n . We can consider an equivalent set of 2 i i +2 i 2 + . . . 2 i j points with starting points 1 /n . From the previous claim, we know that the expected number of unfixed points after T p iterations is 1 2 (2 / p i i + 2 i 2 + . . . 2 i j ) . Since m 2 p = (2 p / 2 i 1 ) 2 · (2 i i ) 2 , the probability of non-absorption is 2 i 1 / 2 p for starting point at 2 i 1 /n , the expected number of unfixed variables are same for both the configurations. So, we can claim the following

Let m p = 2 p for p = 1 2 , . . . log n -c ′ log log n and let T p = m a 2 p 2 γ 2 . Then it follows that after T p steps, the number of variables that are not absorbed is bounded by n 2 p with high probability. More specifically, the number of variables that are not fixed in the interval [ T , T i i +1 ] can be bounded by n 2 i with high probability for i ≤ log n -c ′ log log n .

4 A constraint with n variables has a trivial solution where any one variable can be set to 1.

5 We need not consider smaller values, since there is trivial solution = 1

Lemma 4.1 For any set of points starting at a , i ∑ i a i ≤ 1 , after T p = 2 p · 2 p n 2 · γ 2 steps of random walk, the expected number of points that are unfixed is bounded by O ( n m p ) with high probability for m p ≤ n/logn ) .

## 4.3 Bounding accumulative error

Note that we had appealed to the following (intuitive) observation useful for some later arguments also.

Observation 4.2 Let W 1 and W 2 be two Brownian walks starting from positions a , a 1 2 respectively where a 1 &lt; a 2 . Then after any fixed number of steps t , Pr[ W 1 is absorbed at 0 ] ≥ Pr[ W 2 is absorbed at 0 ]

This follows since any sequence of steps by which W 2 is absorbed at 0 would also lead to W 1 being absorbed at 0. We will compute the error accumulated in each phase p . For convenience, we have classified the random walk phases into three categories early phase referring to p = 1 . . . log n -log log n , middle phase p = log n -3log log n... log n -log log n and last phase comprising of the remaining log log n phases.

Claim 2 The accumulated error in each of the early phases is O ( 1 log n ) with high probability. This implies a total accumulated error of O (1) in the early phases.

Proof: We will prove it by induction on p . For any C j , the probability that the the Brownian motion hits C j is given by Lemma 3.4

$$\Pr [ | Y _ { 1 } ^ { \prime } + Y _ { 2 } ^ { \prime } \dots Y _ { T } ^ { \prime } | > \beta ^ { \prime } ] \leq 2 \exp ( - \beta ^ { \prime 2 } / 2 T )$$

where β ′ = 1 (log n γ ) · √ n , and ∆ = 1 β ′ · γ · √ n . We have actually neglected δ in 1 log n -δ by assuming that δ is o (1 / log n ) 6 . Let T 1 = 1 4 n 2 · γ 2 . Then the probability that C j gets hit is

$$\begin{array} { c } \cdots & \quad \cdots & \quad \cdots & \quad \cdots & \quad \cdots \\ \quad \leq & \exp - ( \frac { 1 / ( \log ^ { 2 } n \gamma ^ { 2 } ) } { 1 / ( 4 \cdot n ^ { 2 } \gamma ^ { 2 } ) } ) & \quad \cdots & \quad \cdots \\ \cdot & \quad \cdots & \quad \cdots & \quad \cdots \\ \end{array}$$

which is ≤ exp -(4 log n ) &lt; 1 n 4 for n/ log 2 n ≥ log n . Since the number of equations m ≤ n 2 , none of the C j with B 0 ( j ) = log n gets hit with high probability. The probability that any other V j with B 0 ( j ) &lt; log n gets hit is less than the expression in equation 2.

The number of iterations in phase p = T p -T p -1 ≤ T p where T p = 2 p 2 p 4 n γ 2 2 ≥ 2 p 4 n log 3 nγ 2 for p ≤ log n -3log log n . We set ∆ = p 1 log n ( = β ′ · γ · √ 2 (log n -p ) ). The high probability bound holds for all the O (log n ) early phases and all the m inequalities from routine Chernoff bounds and the induction (since there must be a phase where it fails for the first time). /Box

Middle phases For phases p = log n -3log log n to log n -log log n + 2log log log n , the above argument extends easily by using ∆ p = 1 log log n and T p ≥ 2 p 4 n log n log log 2 n γ · 2 . By setting β ′ = ∆ p · 1 γ · √ 2 (log n -p ) , we note that recalculating the bound given in Equation 2 yields

$$\exp - ( \frac { 2 ^ { p } / ( n \log \log ^ { 2 } n \gamma ^ { 2 } ) } { 2 ^ { p } / ( 4 n \log n \log \log ^ { 2 } n \gamma ^ { 2 } ) } ) \leq \exp - ( 4 \log n ) = \frac { 1 } { n ^ { 4 } }$$

So the total contribution to the accumulates error in the 2log log n middle phases 7 is bounded by O ( 1 log log n · log log n = O (1) . In conjunction with Claim 2 , we conclude that

6 We will show later that δ &lt; o ( 1 n )

7 the additional O (log log log n ) can be worked out along similar lines

Lemma 4.2 The cumulative accumulated error in early and middle phases can be bounded by O (1) with high probability.

The limitation of the previous analysis is that it doesn't hold in a straight-forward manner for B p ( V j ) ≤ o (log log n ) . We cannot guarantee the rate of absorption of variables according to Claim 1 with high probability as Chernoff bounds is not effective for o (log n ) unfixed variables - refer to the discussion following Claim 1. Consequently, the union bound over the m inequalities is not effective, even for m = Ω( n ) . In this phase, we can resort to an analysis similar to the edge-walk of Lovette and Meka [LM12]. Till now, we could avoid hitting the constraints in each of the phases but, in the subsequent phases we could potentially hit upto Ω( n ) constraint hyperplanes and still we must ensure that a large fraction of (remaining) variables are hit. It will slow down the convergence but we have not formally analyzed this effect. However, the advantage that we have now is the || V j || 2 is bounded by O ( √ log n ) . Applying the method of Lovette Meka would yield a bound of O ( ∑ √ i log( n 2 i ) · log( 2 i m n )) which is Ω(log 2 n ) for m = Ω( n 2 ) .

## 4.4 The last phases of Random walk

Let i = p -(log n -log log n ) where p ≥ log n -log log n is the phase. Continuing with T p = 2 p 4 n log log nγ 2 = log n γ 2 2 i · log log n , it is less than log n γ 2 log log n steps required for the random walk with B V ( j ) ≤ log log n to hit 0. Increasing this would adversely affect equation 2 as the numerator will decrease, no longer giving high probability bounds.

Instead, we now redefine ∆ = ∆ = p ′ i f ( ) i for i = p -(log n -log log n ) where we will determine f ( ) i from the analysis.

We will run it 2 i times longer to boost the probability of success of hitting the variable planes for the 2 log log n -i variables and invoke the result of Lemma 3.2.

Using Lemma 3.4, similar to equation 2, we obtain the probability of hitting a constraint plane

$$\alpha \sigma, \, & \text{manual way you can use your own any or moving a conversion phase} \\ & \leq \, \exp - & ( \frac { \Delta ^ { \prime } _ { i } / ( 2 \log \log n - i, \gamma ^ { 2 } ) } { ( C \cdot ( 2 ) ^ { i } ) / ( 2 \log \log n - i, 2 \log \log n - i, \gamma ^ { 2 } ) } ) \\ & = \, \exp - & ( \frac { f ^ { 2 } ( i ) 2 \log \log n - i / \gamma ^ { 2 } ) } { ( C \cdot ( 2 ) ^ { i } ) / ( \gamma ^ { 2 } ) } ) \\ & = \, \exp - & ( \frac { f ^ { 2 } ( i ) 2 \log \log n } { ( 2 ) ^ { i } 2 ^ { i } - C } ) \\ & \leq \, \quad \frac { 1 } { n ^ { 2 } } \text{ for } f ( i ) \geq \sqrt { C } 2 ^ { i }. \\ \text{all the $m \leq n^{2}$ planes simultaneously, but this yields an error bound of $O(log n \, \cdot$}$$

So it holds for all the m ≤ n 2 planes simultaneously, but this yields an error bound of O (log n · log log n ) .

Suppose we stop at stage i and simply substitute all the remaining variables by 1. We need to balance the error term introduced by the trivial rounding and f ( ) i . Balancing √ C · 2 i and 2 log log n -i , we obtain i = log log n/ 2 -s/ 2) , where s = log C/ 2 . So the final error is 2 log log n/ 2+ s/ 2 = O ( √ log n · log log n ) .

· We briefly outline the possibilities for further improvements of the error bound. The primary contributor came from the inequalities when the number of variables became sub-logarithmic. Since Chernoff bounds could not be applied directly, we had to perform more steps of the random walk leading to the analysis in the previous section of O (log log n · √ log n ) .

For log n -log log n ≤ p ≤ log n -log log n/ 3 , T p = (2) 2(log n -p ) / γ ( 2 ) ≤ O ( 1 γ 2 √ log n ) .

Instead of defining the phases based on the reducing the non-fixed variables by a factor of 2, we will attempt a faster reduction, say from r to √ r . Since the initial phases do not contribute to the error significantly, we will assume that r ≤ log n . This will impact the calculations of Equation 3

Figure 2: An illustration of our rounding procedure

![image](https://ac.marcodsn.me/arxiv-markdown-images/1408.0488v1-figure-1163d899-790a-48be-a8c7-cd13740f2649.jpg)

in the following manner if we try to reduce the size from r to r , ′ r ′ &lt; r in one iteration.

$$& \leq \ \exp - ( \frac { \Delta _ { i } ^ { \prime 2 } / ( r \cdot \gamma ^ { 2 } ) } { ( C \cdot \log n ) / ( r ^ { \prime 2 }, r ^ { \prime }, r ^ { \prime } ) \cdot \gamma ^ { 2 } ) } ) \\ & = \quad \exp - ( \frac { f ^ { 2 } ( i ) r ^ { \prime 4 } } { C \cdot r \cdot \log n } )$$

For r = log n and r ′ = √ log n , we can choose f ( ) i = √ log n for the bound to be less than 1 n 2 . This way we can save an O (log log n ) factor in the error. However, this calculation also reveals the limitation of our analysis for any further improvement, beyond √ log n , say log 1 3 / n .

At this stage, it may be worthwhile to put in perspective and compare our approach with Raghavan-Thompson (RT) rounding. There are actually two rounding procedures used in the algorithm - independent random walks is the one that we analyzed careflly. The other one is the trivial rounding that sets all the unfixed variables in an inequality to 1 and depends on the rate of absorption of the variables. Let us refer to them as Procedure P1 and Procedure P2 respectively. The figure illustrates the effect of P1 and P2 using a graph with x axis as the number of random walk steps T , and the random variables Y i ( T ) and Z i ( T ) representing the behavior of P1 and P2 respectively. These are monotonically increasing and monotonically decreasing respectively and are also correlated. With increasing number of random walk steps, Y i increases starting from Y i = 1 (RHS of inequality) when T = 0 to Y i = ∆ max if we let all walks be absorbed for a large enough T , say T max . If we use Raghavan-Thompson (RT) bound then ∆ max = O (log n/ log log n ) .

We would like to terminate the random walks at some time T ∗ to minimize the sum Y i ( T ∗ ) + Z i ( T ∗ ) . The RT bound corresponds to Y i ( T ) for T ≥ T max and Z i ( T ) = 0 . The paper estimates Y i ( T ) 8 for all T and terminates at some approximation of T ∗ that we use as the terminating condition. Using an explicit stopping condition like Y i ( T ) = Z i ( T ) would yield similar results.

8 If we compare our estimate Y i ( T ) with RT for T ≥ T max ours is slightly inferior, namely O (log n · log log n ) as opposed to log n/ log log n indicating potential for improved analysis.

## 5 Improvements and Generalization

Instead of starting from x ′ i , if we start the random walk from x ′ i D for some D &gt; 1 , we can obtain a rounded value ˆ x i that will intuitively cause smaller violation of the inequalities, but will reduce the value of the objective function. This is similar to damping the probabilistic rounding of Raghavan and Thompson [RT87]. By repeating the calculations done above, we can arrive at the following result for k ≤ log n .

Lemma 5.1 There is a polynomial time randomized algorithm that rounds ¯ x ′ to a random ˆ x ∈ { 0 1 , } n such that

$$1 \leq i \leq m, A _ { i } \cdot \hat { x } \leq O ( 1 )$$

and for all ¯ = ( c c 1 , c 2 ..c n ) c i ≥ 0

$$\mathbb { E } [ < c ^ { T }, \hat { x } > ] = \frac { 1 } { \log n } \cdot < \bar { c } ^ { T }, \bar { x ^ { \prime } } >$$

For 1 ≤ k ≤ log n , we can round to a point ˆ x ∈ { 0 1 , } n such that

$$\begin{array} { c c c } \cdot & \cdot & \cdot & \cdot \\ 1 \leq i \leq m, A _ { i } \cdot \hat { x } \leq O ( \frac { \sqrt { \log n } } { k ^ { 1 / 4 } } ) \end{array}$$

and for all ¯ = ( c c 1 , c 2 ..c n ) c i ≥ 0

$$\mathbb { E } [ < c ^ { T }, \hat { x } > ] = \frac { 1 } { k } \cdot < \bar { c } ^ { T }, \bar { x ^ { \prime } } >$$

Note that the rounding does improve linearly with k since there are now fewer variables above a certain threshold, for which we need to apply the repetition strategy.

The above method does not yield feasible solution to the original packing ILP since we terminate the random walk prematurely before all the variables converge (and set them to 1).

To guarantee feasibility, which is often necessary for approximation algorithms, we can let the random walks terminate which yields results similar to randomized rounding where each variable x i is set to 1 independently with LP solution x ′ i . So, one can obtain bounds similar to Srinivasan [Sri99]. For brevity, we leave out the detailed calculations here. Instead we refer the reader to the technique given in Lemma A.3 that will be useful to derive the bounds with the right value of D .

## 5.1 Final rounding deviation and running time

This aspect is similar in spirit to [LM12] - however, if we limit ourselves to inverse polynomial scaling as opposed to inverse polylogarithmic scaling in [LM12], this becomes a trivial problem by rounding the x ′ i ∈ [1 -δ, 1] to 1 (see Bansal [Ban10]). By choosing δ &lt; 1 n , and γ &lt; δ C √ log n (follows from the normal distibution density function), the total error in an inequality is bounded by n 1 n ≤ 1 . For the purpose of efficiency, we may choose a larger γ, δ and for completeness, we present the analysis in the appendix. There is however an additional issue that we must address, namely, the objective function value. For this, we need to choose a sufficiently small δ , so that when we round x ′ i ∈ [0 , δ ] to 0, we do not lose more than a constant fraction in the objective value. This can be done by choosing δ &lt; min i { x ′ i } . Recall that max i { c i } = 1 , so as long as x ′ i is sufficiently large like an inverse polynomial, this does not present any problems. For instance, if δ &lt; 1 n , then the maximum error is bounded by 1 and clearly, the value of the objective function is at least 1 by setting the x corresponding to the maximum c i as 1. So, it can only affect by a constant factor.

The number of iterations of our rounding procedure is O ( n 3 √ log n ) .

## 6 Applications

As remarked in the introduction, we cannot substitute the rounding technique of Raghavan and Thompson [RT87] for the multi-commodity flow approximation by our algorithm as we do not guarantee that exactly one of the polynomially many paths (variables) corresponding to some sourcedemand flow path will be rounded to 1. However, we can guarantee that a large (constant) fraction of the source-destination pairs will be connected and the capacity will not be violated by more than √ log n instead of O (log n/ log log n ) . We leave out the details from this abstract.

## 6.1 Rounding and discrepancy

Our bounds can be used directly for the weighted MISR (Maximum Independent Set of Rectangles) but our current bound of √ log n does not improve the best known bounds[CC09, LENO04, CHP09] - it must be asymptotically better than √ log n log log n but our general bound for rounding falls short of that. It is also not surprising since we have not used any specific properties of the geometry of the rectangle arrangement. We will actually take a more general approach of relating our bounds with the discrepancy of the underlying set system.

For a given subset system ( V, S ) , where | V | = n and |S| = m , Bansal [Ban10] presents a polynomial time algorithm for explicit construction of hereditary discrepancy, herdisc ( S ) using a semidefinite relaxation of herdisc , called the hereditary vector discrepancy, hervecdisc ( S ). This is done by using the following feasible semi-definite program

$$\| \sum _ { i \in S _ { j } } v _ { i } \| ^ { 2 } \ \leq \ \lambda ^ { 2 } \text{ for each set } S _ { j } \text{ restricted to any subset } W \quad \quad \quad ( 5 ) \\ \| v _ { i } \| ^ { 2 } _ { 2 } \ = \ 1 \ \forall i \in W \\ \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \colon \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \, \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \end{matrix}$$

where λ is the herdisc ( S ). Clearly hervecdisc ( S ) ≤ herdisc ( S ) since it is a relaxation. The algorithm returns a coloring with discrepancy bounded by hervecdisc ( S · log( mn ) ).

Bansal [Ban10] presents an iterative technique based on the idea of partial coloring such that over successive iterations, a constant fraction of the variables get their colouring fixed to {-1 +1 , } . In every iteration, the partial coloring obtained by solving an SDP where the values of x i s in iteration t are updated as follows

( x t ) i = ( x t -1 ) i + s · &lt; g,v i &gt; where s &lt; 1 is a scale factor and g is a vector, each of whose components are chosen independently from N (0 1) , . Note that &lt; g,v i &gt; is also Gaussian with variance = || v i || 2 2 = 1 . Let x /lscript ( C j ) denote the sum of the uncolored variables in C j after /lscript iterations and s = 1 4 n √ log( mn ) is an an appropriate scale factor. Then

$$\Pr [ | x _ { \ell } ( C _ { j } ) | > 2 \sqrt { \log ( m n ) } \cdot \lambda \cdot s \cdot \sqrt { \ell } ] \leq 2 \exp ( - 2 \log ( m n ) ) = \frac { 2 } { m ^ { 2 } n ^ { 2 } } \\ \nolimits = \mathcal { O } ( \frac { 8 \log n } { 2 } ) \,. \, \text{We will make use of the construction in a way that will enable us to make n. }$$

for /lscript = O ( 8 log n s 2 ) . We will make use of the construction in a way that will enable us to make use of the hervecdisc = λ in our rounding algorithm.

Lemma 6.1 The variance of x C ( j ) corresponding to each step of the iteration is λ 2 · s 2 where s is a scale factor. Note that x C ( j ) has a Guassian distribution with expectation 0.

Remark The variance is not directly dependent on || V j || 2 but on the hereditary discrepancy which could be smaller for the subset system.

Equations 2 and 3 can be recalculated on the basis of this new observation in the following

manner.

Let us address Equation 3 since it is more critical for the final bounds.

$$\Pr [ x _ { T } ( C _ { j } ) & \text{ exceeds } \Delta ] \leq \exp { - ( \frac { \Delta ^ { 2 } } { \gamma ^ { 2 } \cdot \lambda ^ { 2 } \cdot T } ) } \\ \tau \text{auction } 3 \sinceq \text{it is more critical for the final bounds.}$$

$$& \cdot \\ & = \exp - ( \frac { f ^ { 2 } ( i ) 2 ^ { 2 ( \log \log n - i } ) / \gamma ^ { 2 } ) } { ( C \cdot ( 2 ) ^ { i } ) \cdot \lambda ^ { 2 } / ( \gamma ^ { 2 } ) } ) \\ & = \exp - ( \frac { f ^ { 2 } ( i ) \log ^ { 2 } n } { ( 2 ) ^ { 3 i } \cdot C \cdot \lambda ^ { 2 } } ) \\ & \leq \exp - ( \frac { f ^ { 2 } ( i ) \log ^ { 2 } n } { C \cdot 2 ^ { 3 i } \cdot p o l y \log \log ( n ) } ) \text{ if } \lambda ( n ) \text{ is bounded by polylog} ( n ) \\ \sum \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \, \sum \, \dots \end{array}$$

Using our earlier strategy of early termination at i = 3 5log log / n , we obtain a bound of 2 2 5 log log / n = log 2 5 / n when discrepancy is bounded by polylog.

It is known that the discrepancy of the the axis parallel rectangles with respect to a set of n points on the plane is O (log 5 2 / n ) [Mat99]. For the MISR problem, we need to bound the discrepancy of the dual range space, i.e. V is a set of n rectangles and S is the set of regions of the arrangement of V which can be bounded by n 2 . Using a construction similar to the primal range space, we can prove a polylog bound on the discrepancy of this subset system. Therefore we can obtain the following approximation for the MISR problem.

Theorem 6.1 There exists a polynomial time algorithm for approximating the optimal solution of any weighted MISR problem within O (log 4 5 / n ) .

## 7 Future work

This is hopefully the beginning of an important direction of research, viz., to explore concrete connections between discrepancy, randomized rounding and approximation algorithms. It is likely that the bounds in this paper will improve with more sophisticated proof techniques that will lead us to better approximation guarantees in a very general framework. The basic rounding algorithm may benefit from a more careful analysis of the edge-walk. Also, to improve the efficiency of the MISR algorithm (or in general small discrepancy system), can we do without repeatedly solving SDP ?

Acknowledgement The author is thankful to Antar Bandhopadhyay for the pointing out the generality of the Optional Stopping theorem and to Dhruv Malhotra and Sayantan Saha for meticulous experiments related to the covergence of the rounding algorithm.

## References

[Ban10] Nikhil Bansal. Constructive algorithms for discrepancy minimization. In FOCS, pages 3-10, 2010.

[CC09]

Parinya Chalermsook and Julia Chuzhoy. Maximum independent set of rectangles. In SODA, pages 892-901, 2009.

[CGKT07] Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, and Kunal Talwar. Hardness of routing with congestion in directed graphs. In STOC, pages 165-178, 2007.

[CHP09]

Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum inde- pendent set of pseudo-disks. In Symposium on Computational Geometry, pages 333-340, 2009.

| [Fel68]   | William Feller. An Introduction to Probability Theory and Its Applications, volume 1,2. Wiley, 1968.                                                                                                                                     |
|-----------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [LENO04]  | Liane Lewin-Eytan, Joseph Naor, and Ariel Orda. Admission control in networks with advance reservations. Algorithmica, 40(4):293-304, 2004.                                                                                              |
| [LM12]    | Shachar Lovett and Raghu Meka. Constructive discrepancy minimization by walking on the edges. In FOCS, pages 61-67, 2012.                                                                                                                |
| [Mat99]   | Jiri Matousek. Geometric discrepancy : an illustrated guide. Algorithms and combina- torics. Springer, Berlin, New York, 1999.                                                                                                           |
| [MU05]    | Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York, NY, USA, 2005.                                                                    |
| [Ros06]   | Sheldon M. Ross. Introduction to Probability Models, Ninth Edition. Academic Press, Inc., Orlando, FL, USA, 2006.                                                                                                                        |
| [Rot13]   | Thomas Rothvoß. Approximating bin packing within o(log opt * log log opt) bins. In FOCS, pages 20-29, 2013.                                                                                                                              |
| [RT87]    | Prabhakar Raghavan and Clark D. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365-374, 1987.                                                                       |
| [Sri95]   | Aravind Srinivasan. Improved approximations of packing and covering problems. In STOC, pages 268-276, 1995.                                                                                                                              |
| [Sri99]   | Aravind Srinivasan. Approximation algorithms via randomized rounding: a survey. Lectures on Approximation and Randomized Algorithms (M. Karonski and H. J. Promel, editors), Series in Advanced Topics in Mathematics, pages 9-71, 1999. |

## A Random Walk approximations and Tail bounds

The following result will be useful for upper and lower bounds on the tail of ( X t ) i .

Observation A.1 (Anthony and Barlett, Neural Network Learning - Theoretical Foundations) Let X be a r.v. distributed as N (0 1) , . Then

$$\frac { 1 } { 2 } \cdot ( 1 - \sqrt { 1 - \exp - x ^ { 2 } } ) \leq \Pr [ X > x ] \leq \frac { 1 } { x \sqrt { 2 \pi } } \exp ( - x ^ { 2 } / 2 )$$

Remark : 1. For x ≥ α , for any α ≥ 1 , there exists a constant 0 &lt; c &lt; 0 5 . such that Pr[ X &gt; x &gt; c ] . 2. One can obtain better values of c from the standard normal curve, close to 0.33.

## A.1 Hitting times of Brownian walk

Following Ross[Ros06], let T a denote the first time the Brownian motion X t ( ) hits a . For a &gt; 0 9 , we can compute Pr[ T a ≤ t ] by conditioning on Pr[ X t ( ) ≥ a ] as

$$\frac { \Pr [ X ( t ) \geq a ] = \Pr [ X ( t ) \geq a | T _ { a } } { \partial \, \dots \, \cdots \, \cdots } \leq t ] \cdot \Pr [ T _ { a } \leq t ] + \Pr [ X ( t ) \geq a | T _ { a } > t ] \cdot \Pr [ T _ { a } > t ] \quad ( 9 )$$

9 Conditioned on this event

Clearly Pr[ X t ( ) ≥ a T | a &gt; t ] = 0 , so

$$\Pr [ X ( t ) \geq a ] = \Pr [ X ( t ) \geq a | T _ { a } \leq t ] \cdot \Pr [ T _ { a } \leq t ]$$

If T a ≤ t , then by the symmetry of the random walk process, X t ( ) can be to either side of a with equal probability, viz., Pr[ X t ( ) ≥ a T | a ≤ t ] = 1 2 . Then we can rewrite the previous equation as

$$\Pr [ X ( t ) \geq a ] \ = \ \frac { 1 } { 2 } \cdot \Pr [ T _ { a } \leq t ] \\ \quad. \ n. t r \tau \ > \mu _ { 1 } \quad \partial _ { 1 } \ n. t r \nu _ { 1 } / \mu _ { 1 } \searrow \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \colon$$

$$\Rightarrow \Pr [ T _ { a } \leq t ] \ = \ \ 2 \cdot \Pr _ { \substack { 2 \cdot \Pr [ X ( t ) \geq a ] \\ 2 \cdot \Pr ^ { \infty } \quad _ { 2 \cdot \infty } } },$$

$$= \ \frac { \overset { \nu \, z n \, \iota } { 2 } } { \sqrt { 2 \pi } } \cdot \int _ { a / \sqrt { t } } ^ { \infty } e ^ { - y ^ { 2 } / 2 } d y \, \text{using } x = y \sqrt { t }$$

$$\psi _ { \{ \psi ^ { 2 } a \, = \, \nu _ { 1 } } & = - \, \psi _ { 1 } \, \psi _ { 2 } \, \psi _ { 3 } \, \psi _ { 4 } \, = \, \psi _ { 5 } \, \psi _ { 6 } \, \psi _ { 7 } \, \\ & = \, \frac { 2 } { \sqrt { 2 \pi t } } \cdot \int _ { a } ^ { \infty } e ^ { - x ^ { 2 } / 2 t } d x \\ & \quad 2 \quad \int _ { a } ^ { \infty } \quad - \psi _ { 2 } ^ { 2 } / 2 \,, \quad. \quad \, \tau _ { 1 } \, = \, \psi _ { 2 } \,.$$

(14)

The probability that the walker gets absorbed within t steps at an absorbing barrier at B = Pr[max 0 ≤ ≤ s t X s ( ) ≥ B ]

$$& = \Pr [ T _ { B } \leq t ] \\ & - \mathfrak$$

$$& - \stackrel { \lambda \lambda \lambda \lambda \lambda \lambda \lambda \lambda$$

$$= \underset { 2 \quad \int } { 2 \quad \int } \Pr [ X$$

$$\begin{array} {$$

where the last inequality follow from ∫ ∞ -x e y 2 / 2 dy ≥ 1 2 [1 -√ 1 -e -x 2 ] . By substituting t = αB 2 for some α &gt; 1 , we obtain

$$\Pr [ T _ { B } \leq t ] \ & \geq \ ( 1 -$$

$$= \begin{array} {$$

$$\omega ^ { - - } \, \tilde { \lambda } ^ { - }$$

$$\geq \ 1 - O ( \frac { 1 } { \sqrt { \alpha } } )$$

We can summarize as follows.

Lemma A.1 Let X be a r.v. corresponding to a symmetric Brownian walk with standard normal distribution N (0 1) , in an interval [ -L, + U ] starting from 0 with absorbing barriers at the boundaries. Then the probability that the walk is absorbed at -L after α · L 2 steps conditional 10 to not being absorbed at + U is given by

$$\Pr [ T _ { L } ( X ) > \alpha \cdot L ^ { 2 } ]$$

By symmetry, if T U ( X ) denotes the number of steps to be absorbed at + U ,

10 the previous calculation was for the first passage time not involving absorption

$$\Pr [ T _ { U } ( X ) > \beta \cdot U ^ { 2 } ]$$

## Proof: ( of Lemma 3.1)

We will show that with high probability a fixed walk terminates within O r ( 2 log m ) with probability exceeding 1 -1 m 2 . This will imply the Lemma using a straightforward union bound. Divide the αr 2 log m steps into (almost) equal sized α log m phases for some appropriate constant α . The probability that the walk doesn't hit the barriers in α r · 2 steps is less than 1 2 / from Lemma A.1 for α ≥ 4 . So the probability that it will not hit the barriers in α log m phases is less than ( 1 2 ) α log m ≤ 1 m 2 . /Box In some situations, it suffices that a large fraction of the walks terminates, that can be achieved in fewer steps. In this context the following strategy for boosting the success probability will be useful.

## A.2 Boosting success probability using repetition

Consider k ≤ log n unbiased coins. The expected number of heads that we obtain with independent tosses is Ω( k/ 2) , that holds with probability 1 -1 e Ω( k ) from Chernoff bounds. To boost this probability to inverse polynomial in n (for log k /lessmuch log n ), we use repeated tossing in the following manner. Each coin is tossed repeatedly α · log n k times for some suitable constant α and if any of those tosses, we obtain a head, it is considered a success. Then the probability of the number of successes being less than k/ 2 (there can be at most one success for a coin), is bounded by the probability of obtaining fewer than k/ 2 heads is ∑ i = k i = k/ 2 ( ) k i 1 2 iα log n/k · (1 -1 2 α log n/k ) k -i ≤ k/ 2 · 2 k · 1 n α/ 2 . For k &lt; log n , this is inverse polynomial in n for α &gt; 4 .

The above argument can be easily generalized for any constant probability of success, say 0 &lt; p &lt; 1 2 / , and more than c · k successes for 1 &gt; c &gt; 1 2 / by suitably increasing α .

Lemma A.2 Let X , i 1 ≤ i ≤ k ≤ log n be k independent random variables such that Pr[ X i = 1] = p i ≥ p . Let X i,j , i = 1 2 , . . . k, j = 1 2 , . . . α log n/k be random variables representing α log n/k independent instances of X i . Let Y i = 1 , if at least one of the X i,j = 1 for j = 1 2 , . . . α log n/k . Then Y = ∑ i Y i ≥ c · k with high probability for any fixed c &lt; 1 and p &gt; 0 for an appropriate choice of α = Ω( 1 (1 -c ) log(1 · / (1 -p )) .

The above observation will be used to increase probability of absorption of a random walk.

Corollary A.0.1 For any constant 0 &lt; c &lt; 1 , at least c · k random walks among k &lt; log n random walks starting from 0 in the interval [ -r, + ] r will be absorbed at the end-points of the interval within O r ( 2 ( log n k +1) steps with probability ≥ 1 -1 n 2 .

Proof: Divide the random walk into α log n k phases of r 2 steps. Let Y i,j = 1 if the i -th random walk, 0 ≤ i ≤ k terminates in the j -th phase 0 otherwise. Note that Pr[ Y i,j = 1] = 1 / 2 and these are independent. Suppose, the random walks were being done sequentially till it was absorbed. This situation is analogous to the previous coin tossing experiment and the required probability bound follows. Note that the assumption of sequential experiments does not affect the probabilistic bounds. /Box

## Proof of Lemma 3.2

The sub-interval [0 , 2 a ] can be mapped to the interval [ -r, + ] r and we can record the first passage time to 0 and 2 a . From the previous result, at least ck random walks with pass through either of the end-points within O a ( 2 ( log n k +1) steps. The proof follows from using a symmetry argument, as a walk is equally likely to be absorbed in 0 and 2 a .

## Proof: of Lemma 3.3

The proof of the gambler's ruin problem actually uses a quadratic martingale 11 B 2 ( ) t -t where B t ( ) is the Brownian motion random variable. Using the optional stopping theorem on this, we obtain

$$E [ B ^ { 2 } ( T ) - T ] = E [ B ^ { 2 } ( 0 ) - 0 ] = a ^ { 2 }$$

Since p = b a + b is the probability that it is at 0, we obtain E T [ ] = a · b .

Now, consider the events leading to the failure of being absorbed at 0 - these correspond to the absorption of the random walk at either ends or the non-absorption at either ends.

$$\Pr [ F a i l u r e ] = \Pr [ F a i l u r e \cap A b s o r p t i o n ] + \Pr [ F a i l u r e \cap N o n - a b s o r p t i o n ]$$

= Pr[ Failure Absorption | ] · Pr[ Absorption ] + Pr[ Failure Non | -absorption ] · Pr[ Non -absorption ]

$$\leq \Pr [ F a i l u r e | A b s o r p t i o n ] + \Pr [ N o n - a b s o r p t i o n ] \\.. \quad \. \ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \end{$$

From the preceding argument ,the probability that the random walk is not absorbed after kab steps is less than 1 /k uding Markov's inequality. From optional stopping criteria, the probability of absorption at 0 is b a + b . The probability that the random walk is not absorbed at 0 after kab steps is bounded by 1 -b a + b +1 /k . Consequently, the probability of being absorbed at 0 is at least b a + b -1 /k . /Box

The above Lemma will be used repeatedly in the following generalization of a random walk W starting from an arbitrary location. Suppose W begins from location a in an interval of length L /greatermuch a . Let b i = (1 + ε ) i · a , with b 0 = a for some constant ε &gt; 0 . Let us denote the random walk in the interval [0 , b i ] starting at b i -1 by E i which is the i -th epoch . One of the following may happen -

- (i) either W gets absorbed at 0 before the i -th epoch, or
- (ii) W may get absorbed at 0 during the i -th epoch or
- (iii) W may cross b i and start the i +1 -st epoch

Let X , i i = 1 2 , , . . . be an indicator random variable that is 1 when the following are true and 0 otherwise

- (A) W enters the i -th epoch or
- (B) W is absorbed at 0 during the i -th epoch and
- W takes less than T i = 16(1 + ε ) 2( i -1) a 2 +16(1 + ε ) 2 i a 2 steps.

Then Pr[ X i = 1 | X i -1 = 0] ≥ 1 -( 1 1+ ε + 1 4) / = ε 1+ ε -1 4 / ≥ 1 5 / for ε ≥ 3 4 / . Equivalently Pr[ X i = 0 | X i -1 = 0] ≤ 4 5 / . Since Pr[ X i = 0 | X i -1 = 1] = 0 , the unconditional probability Pr[ X i = 0] ≤ 4 5 / . The probability that the first t X i 's are 0 is ≤ 4 t 5 t .

In case W takes more than T i steps, then the next epoch starts to the left of b i and so the Pr[ X i = 1] increases. The value of ε can be reduced by allowing more steps to enter the next epoch, i.e., it can be made arbitrarily small and still Pr[ X i = 0] &lt; 1 .

In conjunction with the strategy for repetition in Lemma A.2, we will summarize the above result as follows that will be useful in the context of our analysis of the last phases.

Lemma A.3 Consider k &lt; log n random walks starting at locations less than a . Then, for any 0 &lt; c , ε &lt; 1 1 at least c 1 k of the walks are absorbed with high probability after c 2 (1 + ε ) (2 log n /k ) · a 2 steps for some c 2 &gt; 1 (depending on c 1 , ε ).

11 The proof that it is a martingale can be found in standard books on stochastic process

## A.3 Rounding calculations for larger step-size

We present the detailed calculations for completeness.

Consider a sequence of random variables x , x 1 2 . . . x n where x i ∈ [0 , δ ] ∪ [1 -δ, 1] for some 0 &lt; δ &lt; 1 . Define

$$Z _ { i } = \begin{cases} 1 & \text{with probability $x_{i}$} \\ 0 & \text{otherwise} \end{cases}$$

which is based on the conventional randomized rounding. Let the difference vector Y be defined as Y i = Z i -x i for all i . Then

$$\mathbb { E } [ Y _ { i } ] = \mathbb { E } [ Z _ { i } - x _ { i } ] = \mathbb { E } [ Z _ { i } ] - x _ { i } = x _ { i } - x _ { i } = 0$$

Moreover

$$\mathbb { E } [ Y _ { i } ^ { 2 } ] = \mathbb { E } [ ( Z _ { i } - x _ { i } ) ^ { 2 } ] = \mathbb { E } [ Z _ { i } ^ { 2 } + x _ { i } ^ { 2 } - 2 Z _ { i } \cdot x _ { i } ] = \mathbb { E } [ Z _ { i } ^ { 2 } ] + x _ { i } ^ { 2 } - 2 \cdot x _ { i } \cdot \mathbb { E } [ Z _ { i } ]$$

which is E [ Z 2 i ] -x 2 i . So E [ Y 2 i ] can be upper-bounded by

$$\max _ { x _ { i } \colon 1 - \delta \leq x _ { i } \leq 1 \cup 0 \leq x _ { i } \leq \delta } \mathbb { E } [ Z _ { i } ^ { 2 } ] - x _ { i } ^ { 2 }$$

Note that E [ Z 2 i ] = 1 2 · x i = x i . So the above expression is

$$\max _ { x _ { i } \colon 1 - \delta \leq x _ { i } \leq 1 \cup 0 \leq x _ { i } \leq \delta } x _ { i } ( 1 - x _ { i } ) ] = \max \{ \delta ( 1 - \delta ), \delta ( 1 - \delta ) \}$$

which is bounded by δ . The variance

$$\sigma ^ { 2 } ( Y _ { i } ) = \mathbb { E } [ ( Y _ { i } - E [ Y _ { i } ] ) ^ { 2 } ] = \mathbb { E } [ Y _ { i } ^ { 2 } ] \leq \delta$$

Lemma A.4 Let V be an n dimensional 0-1 vector, and Y = [ Y , Y i 2 , . . . Y n ] . Then variance of the dot-product σ 2 ( V · Y ) ≤ n · δ as Y i are independent.

Using Chernoff bounds on the random variable W = ( V · Y -E V [ · Y ]) 2 = ( V · Y ) 2 (since E Y [ i ] = 0 ) we obtain

$$\Pr [ W \geq ( 1 + \Delta ) E [ W ] ] \leq \left [ \frac { e ^ { \Delta } } { \left ( 1 + \Delta \right ) ^ { 1 + \Delta } } \right ] ^ { E [ W ] }$$

where E W [ ] = σ 2 [ V · Y ] ≤ nδ .

$$\Pr [ W \geq ( 1 + \Delta ) n \delta ] \leq \$$

Using δ = c n ∆ , c ≥ 1 , in the previous inequality, we obtain,

$$\Pr [ W \geq c + 1 ] \ \leq \ \left [ \frac {$$

$$\leq \ \frac { 1 } { 2 ^ { c } \cdot m } \text$$

$$\begin{array} {$$

Lemma A.5 Given an n dimensional 0 1 , vector V and the difference vector Y , obtained from rounding a vector Z where Z i ∈ [0 , δ ] ∪ [1 -δ, 1] with δ ≤ c n m · 1 /c ,

$$\Pr [ | V \cdot Y | \geq \sqrt { c + 1 } ]$$

This implies that for any m 0-1 vectors V , V 1 2 · V m , by using the union bound

Lemma A.6 The probability that any of the dot products V i · Y , 1 ≤ i ≤ m exceeds √ c +1 is less than 1/ 2 c .
Sandeep Sen
Improved Randomized Rounding using Random Walks
We describe a novel algorithm for rounding packing integer programs based on
multidimensional Brownian motion in $\mathbb{R}^n$. Starting from an optimal
fractional feasible solution $\bar{x}$, the procedure converges in polynomial
time to a distribution over (possibly infeasible) point set $P \subset {\{0,1
\}}^n$ such that the expected value of any linear objective function over $P$
equals the value at $\bar{x}$. This is an alternate approach to the classical
randomized rounding method of Raghavan and Thompson \cite{RT:87}.
  Our procedure is very general and in conjunction with discrepancy based
arguments, yield efficient alternate methods for rounding other optimization
problems that can be expressed as packing ILPs including disjoint path problems
and MISR.