The Lower Bound Estimations of A ProbabilityMinimization ProblemSun Churen ∗Huang Lei †AbstractThis article considers the problem of min ξP r (|ξT x |≤α)s.t. ξ 2=1.We first concentrate on the case that x i ,i =1,···,n are binary random variable with identical probability distribution and derive a lower bound estimation.And then we observe the case that x is a random normal vector and obtain some lower bound estimations.Keywords.Probability optimization problem,Lower bound estimation,Binary random variable,Random normal vector.AMS subject classification.90C15,90B99,62H10.1IntroductionWe consider the following probability optimization problem in this article:min P r (| n i =1ξi x i |≤α)s.t. ξ 2=1(1.1)where α≥0,ξ=(ξ1,···,ξn )T ∈R n ,x =(x 1,···,x n )T and x i ,i =1,···,n are identically independent random variables with probability distributions P r (x i =12)=1,n ,wheW e consider theFirstly ,it is a concrein [5],[11]).Secondl estimate the comple to pro v e whether a g in engineering can b F or the problem b een obtained up tivarianceσ,then the Chebychev’s inequality(see in[3],[8])shows that there is a two-sided inequality for anyα≥0P r(|X−µ|≥α)≤σ2/α2while the one-sided Chebychev’s inequality(see in[3],[8])saysP r(X−µ≥α)≤σ2/(α2+σ2)Then by symmetry,one concludes that for anyα≥0,there is P r(|X−µ|≥α)≤2σ2/(α2+σ2).If x i,i=1,···,m are identically independent random variables with probability dis-tributions P r(x i=0)=1−p and P r(x i=1)=p,and let Bin(n,p)= n i=1x i,then the Chernoffbound(see in[8])shows that for any0<a≤np,there isP r(|Bin(n,p)−np|>a)<2e−a2/3npAs an improving,the Hoeffeling Azuma inequality(see in[8])claims that if X is a random variable determined by n trials T1,···,T n and it satisfies for each i,i=1,···,nmax|E(X|T1,···,T i+1)−E(X|T1,···,T i)|≤c iwhere this maximum is taken over all possible outcomes of T1,···,T i+1and E(X|T1,···,T i) is the conditional expected value of X conditioned on the outcomes of T1,···,T i,thenP r(|X−E(X)|>t)≤2e−t2/(2 n i=1c2i)For an extension of problem(1.1),Pinelis(see in[6])obtained a multidimensional ver-sion of the following inequalityP r(ξ1x1+···+ξn x n≥α)≤cP r(ζ≥α)=c(1−Φ(α)),∀α∈Rwhere x i s are independent Rademacher random variables,ζis a standard norm random variables andΦis its distribution function whileξ i s are real numbers such that b 2=1 and c=2e3/9.Furthermore,Pinelis(see in[7])obtained an improved result as following. If ξ 2=n and x i,···,x n are independent Rademacher random variables,the for all α∈2Z−n,there isP r(ξ1x1+···+ξn x n≥α)≤c P r(ξ1+···+ξn≥α)where c=2e3/4=4.46....Along another line,A.Ben-Tal and A.Nemirovski(see in [1])get a better result for the case that x i,i=1,···,n are identically independent with probability distributions P r(x i=1)=P r(x i=−1)=1/2,i=1,···,n in a different way.Their result shows forα=1that there is1P r(|ξT x|)≥2The Case That x i,i=1,···,n are identically inde-pendent with probability distributions P r(x i=1)= P r(x i=−1)=1/2,i=1,···,nIn this section,we consider the problem(1.1)in the case that x i,i=1,···,n are identically independent with probability distributions P r(x i=1)=P r(x i=−1)=1/2, i=1,···,n.We will derive a general lower bound estimation of it under appropriate conditions.First,the follow result is needed.Theorem2.1Let the random variables x1,···,x n be independent with x i−E(x i)≤b for each i=1,···,n.Let S n= n i=1x i and let S n have expected valueµand varianceσ(the sum of the variances of x i,i=1,···,n).Then for any t≥0there isP r(S n−µ≥t)≤e−(σ/b2)((1+ )ln(1+ )− )(2.2) To prove this theorem,we need the following lemma.Lemma2.1Let g(x)=(e x−1−x)/x2.If x=0,then g(x)is increasing.And if the random variable satisfies E(x)=0and x≤b,then there isE(e x)≤e(g(b))var(x)(2.3) Proof.That g(x)is increasing is obvious.In fact,we haveg (x)=x−3((x−2)e x+x+2)So it suffices to show that h(x)=e x(x−2)+2+x≥0for all x.Now h(0)=0and h (x)=(x−2)e x+1.Then h (0)=0and h (x)=xe x.So h (x)<0for all x<0and h (x)>0for all x>0.Thus h(x)≥0as required.For the second part of the lemma,note thate x=1+x+x2g(x)≤1+x+x2g(b)for all x≤b.Hence if E(x)=0and x≤b,thenE(e x)≤1+g(b)var(x)≤e g(b)var(x)as required.2 Now we come to prove theorem2.1.Proof.By lemma2.1,∀h,we haveE(e h(S n−µ))=Πn k=1E(e h(x k−E(x k))≤e g(hb)h2vHence by Markov’s inequality,∀h≥0,there isP r(S n−µ≥t)≤e−ht E(e h(S n−µ))≤e−ht+g(hb)h2v(2.4)To minimize the bound,we set h=1σ),and then we get(2.2).2From theorem2.1,we get the following corollary.Corollary 2.1Let x i =±1,i =1,···,n with probability distribution P r (x i =1)=P r (x i =−1)=1/2.Let ξsatisfy ξ 2=1.Then we haveP r (|S n −E (S n )|≤α)=P r (|ξT x |≤α)≥1−2e −((1+α)ln (1+α)−α)(2.5)Proof.As S n = n i =1X i =ξT x = n i =1ξi x i ,where X i =ξi x i ,i =1,···,n ,we get E (S n )=0,var (S n )=n i =1ξ2i =1Hence we have µ=E (S n )= ni =1ξi E (x i )=0,σ=1and |X i −E (X i )|=|ξi x i |=|ξi |≤1=b so =αas in theorem 2.2.Via theorem 2.2,we getP r (|S n −µ|≤α)=1−2P r (S n −µ≥α)(2.6)≥1−2P r (S n −0≥α)≥1−2e −((1+α)ln (1+α)−α)as the corollary declaimed.2One can see that when α=1,the declaration of corollary 2.1becomesP r (|ξT x |≤1)≥e −23where ξis constrained by ξ 2=1.But our result is based on a general setting and αis just required to be larger than or equal to 0.3The Case That x is a Random Vector with NormalDistributionThis section focus on the case that x is a normal random vector which follows N (¯x ,Σ),i.e.,x has a mean value ¯x and a covariance matrix Σ.Then the density function of x is as followsf (x )=12(det (Σ))−12(x −¯x )T Σ−1(x −¯x ))(3.7)where det (Σ)denotes the determinant of Σ.For α≥0,we consider the following problem(P )min x P r (|ξT x |≤α)s.t. ξ 2=1(3.8)First,we introduce the following theorem,which can be found in general textbook of multivariate analysis(eg.see in [2],[9],[13]).Theorem 3.1Let A be a operator mapping R n to R m .Suppose x ∼N (¯x ,Σ),then A x ∼N (A ¯x ,A ΣA T ),where A T is the conjugate operator mapping R m to R n .Let’s come to consider P r (|ξT x |≤α).AsP r (|ξT x |≤α)=P r (−α≤ξT x ≤α)(3.9)=P r (ξT x ≤α)−P r (ξT x ≤−α)Then by theorem 3.1,we haveP r (|ξT x |≤α)=α−α12(ξT Σξ)12(y −ξT ¯x )(ξT Σξ)−1(y −ξT ¯x ))dy =12(ξT Σξ)12ξT Σξ(y −ξT ¯x )2)dy=12(ξT Σξ)12ξT Σξθ2)dθ=12 α−ξT ¯x ξT Σξ−α−ξT ¯x ξT Σξexp (−1√√λmin (Σ))−13.The caseΣ=I n,¯x=0,where I n is the n-dimensional unitary matrix.In this case,ξTΣξ=1andf(ξ)=Φ(α−ξT¯x)−Φ(−α−ξT¯x)Letθ=ξT¯x,theng(θ)=Φ(α−θ)−Φ(−α−θ)One can show that g(θ)is an increasing function with respect toθ≥0.In fact,g (θ)=φ(−α−θ)−φ(α−θ)(3.13)=12π(exp(−12(α−θ)2))≥0,∀θ≥0Hence to let minξP r(|ξT¯x|≤α)be as larger as possible,one needs only to maximize ξT¯x with respect to the constraint ξ 2=1.,i.e.,one needs only to considermaxξT¯x s.t. ξ 2=1(3.14) Via Lagrangian’s method,we get the optimalξto be¯xTheorem 3.2Let x be a random vector following N (¯x ,Σ).For the problem of f ∗=min ξ 2=1P r (|ξT x |≤α),in the case that ¯x =0and Σ=I n ,there is f ∗≥2Φ(α)−1;in the case that ¯x =0and Σ=I n ,there is f ∗≥2Φ(α√ [10]P.R.Garvey,Probability methods for cost uncertainty analysis:a systems engineer-ing perspective,M.Dekker,2000.[11]V.H.Vu,On the Concentration of Multivariate Polynomials with Small Expectation.[12]V.N.Sachkov,Probabilistic methods in combinatorial analysis,Cambridge;NY:Cambridge University Press,1997.[13]W.J.Krzanowski and F.H.C.Marriott,Multivariate analysis,Halsted Press,1994-1995.。
