imported>Etone |
|
| Line 1: |
Line 1: |
| = Lovász Local Lemma=
| | {{MagneticCircuitSegments}} |
| Suppose that we are give a set of "bad" events <math>A_1,A_2,\ldots,A_n</math>. We want to know that it is possible that none of them occurs, that is:
| | '''Permeability''' is a [[property]] of a material that describes how [[density|dense]] a [[magnetism|magnetic field]] would be if the same amount of [[electric current|current]] was passed through it. Permeability is measured in henries per [[metre]] (H/m) and its symbol is <math>\mu</math>. |
| :<math>
| |
| \Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]>0.
| |
| </math>
| |
| Obviously, a ''necessary'' condition for this is that for none of the bad events its occurrence is certain, i.e. <math>\Pr[A_i]<1</math> for all <math>i</math>. We are interested in the ''sufficient'' condition for the above. There are two easy cases:
| |
| ;Case 1<nowiki>: mutual independence.</nowiki>
| |
| If all the bad events <math>A_1,A_2,\ldots,A_m</math> are mutually independent, then
| |
| :<math>
| |
| \Pr\left[\bigwedge_{i=1}^m\overline{A_i}\right]=\prod_{i=1}^m(1-\Pr[A_i])
| |
| </math>
| |
| and hence this probability is positive if <math>\Pr[A_i]<1</math> for all <math>i</math>. | |
|
| |
|
| ;Case 2<nowiki>: arbitrary dependency.</nowiki>
| | Since [[vacuum|empty space]] has a [[constant]] permeability (called the '''permeability of free space''' or <math>\mu_{0}</math>) of exactly <math>0.0000004 \times \pi</math>, most materials are listed with a ''relative permeability'' (symbol <math>\mu_{r}</math>). Relative permeability is the permeability of the material divided by the permeability of free space (<math>\mu_{r} = \mu / \mu_{0}</math>). The permeability of most materials is very close to 1. That means that the permeability of most materials is close enough that we can typically ignore it and use the permeability of free space instead.<ref>Lines and Fields in Electronic Technology, Stanley and Harrington pg 13</ref> The biggest exceptions are materials called [[ferromagnetism|ferromagnetic materials]]. Some examples are [[iron]] (5000) and [[nickel]] (600). Some materials have been specially designed to have a permeability one million times larger than empty space.<ref>http://info.ee.surrey.ac.uk/Workshop/advice/coils/mu/#mur</ref> |
| On the other extreme, if we know nothing about the dependencies between these bad event, the best we can do is to apply the union bound:
| |
| :<math>
| |
| \Pr\left[\bigwedge_{i=1}^m\overline{A_i}\right]\ge 1-\sum_{i=1}^m\Pr\left[A_i\right],
| |
| </math> | |
| which is positive if <math>\sum_{i=1}^m\Pr\left[A_i\right]<1</math>. This is a very loose bound, however it cannot be further improved if no further information regarding the dependencies between the events is assumed.
| |
|
| |
|
| == Lovász Local Lemma (symmetric case) == | | == References == |
| In most situations, the dependencies between events are somewhere between these two extremal cases: the events are not independent of each other, but on the other hand the dependencies between them are not total out of control. For these more general cases, we would like to exploit the tradeoff between probabilities of bad events and dependencies between them.
| | {{reflist}} |
|
| |
|
| The Lovász local lemma is such a powerful tool for showing the possibility of rare event under ''limited dependencies''. The structure of dependencies between a set of events is described by a '''dependency graph'''.
| | [[Category:Electromagnetism]] |
| | |
| {{Theorem
| |
| |Definition (dependency graph)|
| |
| :Let <math>A_1,A_2,\ldots,A_m</math> be a set of events. A graph <math>D=(V,E)</math> with set of vertices <math>V=\{A_1,A_2,\ldots,A_m\}</math> is called a '''dependency graph''' for the events <math>A_1,\ldots,A_m</math> if for each <math>i</math>, the event <math>A_i</math> is mutually independent of all the events in <math>\{A_j\mid (A_i,A_j)\not\in E\}</math>.
| |
| }}
| |
| The maximum degree <math>d</math> of the dependency graph <math>D</math> is a very useful information, as it tells us that every event <math>A_i</math> among <math>A_1,A_2,\ldots,A_m</math> is dependent with how many other events at most.
| |
| | |
| ;Remark on the mutual independence
| |
| :In probability theory, an event <math>A</math> is said to be independent of events <math>B_1,B_2,\ldots,B_k</math> if for any disjoint <math>I^+,I^-\subseteq\{1,2,\ldots,k\}</math>, we have
| |
| :::<math>\Pr\left[A\mid \bigwedge_{i\in I^+}B_i,\bigwedge_{i\in I^-}\overline{B}_i \right]=\Pr[A]</math>,
| |
| :that is, occurrences of events among <math>B_1,B_2,\ldots,B_k</math> have no influence on the occurrence of <math>A</math>.
| |
| | |
| ;Example
| |
| :Let <math>X_1,X_2,\ldots,X_n</math> be a set of ''mutually independent'' random variables. Each event <math>A_i</math> is a predicate defined on a number of variables among <math>X_1,X_2,\ldots,X_n</math>. Let <math>\mathsf{vbl}(A_i)</math> be the unique smallest set of variables which determine <math>A_i</math>. The dependency graph <math>D=(V,E)</math> is defined as that any two events <math>A_i,A_j</math> are adjacent in <math>D</math> if and only if they share variables, i.e. <math>\mathsf{vbl}(A_i)\cap\mathsf{vbl}(A_j)\neq\emptyset</math>.
| |
| | |
| The following theorem was proved by Erdős and Lovász in 1975 and then later improved by Lovász in 1977. Now it is commonly referred as the '''Lovász local lemma'''. It is a very powerful tool, especially when being used with the probabilistic method, as it supplies a way for dealing with rare events.
| |
| | |
| {{Theorem
| |
| |Lovász Local Lemma (symmetric case)|
| |
| :Let <math>A_1,A_2,\ldots,A_m</math> be a set of events, and assume that the followings hold:
| |
| #<math>\Pr[A_i]\le p</math> for every event <math>A_i</math>;
| |
| #every event <math>A_i</math> is mutually independent of all other events except at most <math>d</math> of them, and
| |
| :::<math>\mathrm{e}p(d+1)\le 1</math>.
| |
| :Then
| |
| ::<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]>0</math>.
| |
| }}
| |
| Here <math>d</math> is the maximum degree of the dependency graph <math>D</math> for the events <math>A_1,\ldots,A_m</math>.
| |
| | |
| Intuitively, the Lovász Local Lemma says that if a rare (but hopefully possible) event is formulated as to avoid a series of bad events simultaneously, then the rare event is indeed possible if:
| |
| * none of these bad events is too probable;
| |
| * none of these bad events is dependent with too many other bad events;
| |
| And the tradeoff between "too probable" and "too many" is precisely captured by the <math>\mathrm{e}p(d+1)\le 1</math> condition.
| |
| | |
| ==Lovász Local Lemma (asymmetric case)==
| |
| We will prove a general version of the local lemma, where the events <math>A_i</math> are not symmetric. This generalization is due to Spencer.
| |
| {{Theorem
| |
| |Lovász Local Lemma (general case)|
| |
| :Let <math>\mathcal{A}=\{A_1,A_2,\ldots,A_m\}</math> be a set of events, where every event <math>A_i\in\mathcal{A}</math> is mutually independent of all other events excepts those in its neighborhood <math>\Gamma(A_i)\,</math> in the dependency graph. Suppose there exist real numbers <math>\alpha_1,\alpha_2,\ldots, \alpha_m\in[0,1)</math> such that for every <math>A_i\in\mathcal{A}</math>,
| |
| ::<math>\Pr[A_i]\le \alpha_i\prod_{A_j\in\Gamma(A_i)}(1-\alpha_j)</math>.
| |
| :Then
| |
| ::<math>\Pr\left[\bigwedge_{A_i\in\mathcal{A}}\overline{A_i}\right]\ge\prod_{i=1}^m(1-\alpha_i)</math>.
| |
| }}
| |
| This generalized version of the local lemma immediately implies the symmetric version of the lemma: namely, <math>\Pr\left[\bigwedge_{i}\overline{A_i}\right]>0</math> if <math>\Pr[A_i]\le p</math> for all <math>A_i</math> and <math>\mathrm{e}p(d+1)\le 1</math> where <math>d</math> is the maximum degree of the dependency graph.
| |
| To see this, let <math>x_i=\frac{1}{d+1}</math> for all <math>i=1,2,\ldots,n</math>. Note that <math>\left(1-\frac{1}{d+1}\right)^d>\frac{1}{\mathrm{e}}</math>.
| |
| | |
| If the following conditions are satisfied:
| |
| :#for all <math>1\le i\le n</math>, <math>\Pr[A_i]\le p</math>;
| |
| :#<math>ep(d+1)\le 1</math>;
| |
| then for all <math>1\le i\le n</math>,
| |
| :<math>\Pr[A_i]\le p\le\frac{1}{e(d+1)}<\frac{1}{d+1}\left(1-\frac{1}{d+1}\right)^d\le x_i\prod_{(i,j)\in E}(1-x_j)</math>.
| |
| Due to the local lemma for general cases, this implies that
| |
| :<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]\ge\prod_{i=1}^n(1-x_i)=\left(1-\frac{1}{d+1}\right)^n>0</math>.
| |
| This proves the symmetric version of local lemma.
| |
| | |
| We then give the proof of the generalized Lovász Local Lemma. The proof is non-constructive and is by induction.
| |
| {{Proof|
| |
| We can use the following probability identity to compute the probability of the intersection of events:
| |
| {{Theorem|Lemma 1|
| |
| :<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]=\prod_{i=1}^n\Pr\left[\overline{A_i}\mid \bigwedge_{j=1}^{i-1}\overline{A_{j}}\right]</math>.
| |
| }}
| |
| | |
| == A non-constructive proof of LLL ==
| |
| | |
| {{Proof|
| |
| By definition of conditional probability,
| |
| :<math>
| |
| \Pr\left[\overline{A_n}\mid\bigwedge_{i=1}^{n-1}\overline{A_{i}}\right]
| |
| =\frac{\Pr\left[\bigwedge_{i=1}^n\overline{A_{i}}\right]}
| |
| {\Pr\left[\bigwedge_{i=1}^{n-1}\overline{A_{i}}\right]}</math>,
| |
| so we have
| |
| :<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_{i}}\right]=\Pr\left[\bigwedge_{i=1}^{n-1}\overline{A_{i}}\right]\Pr\left[\overline{A_n}\mid\bigwedge_{i=1}^{n-1}\overline{A_{i}}\right]</math>.
| |
| The lemma is proved by recursively applying this equation.
| |
| }}
| |
| | |
| Next we prove by induction on <math>m</math> that for any set of <math>m</math> events <math>i_1,\ldots,i_m</math>,
| |
| :<math>\Pr\left[A_{i_1}\mid \bigwedge_{j=2}^m\overline{A_{i_j}}\right]\le x_{i_1}</math>.
| |
| The local lemma is a direct consequence of this by applying Lemma 1.
| |
| | |
| For <math>m=1</math>, this is obvious. For general <math>m</math>, let <math>i_2,\ldots,i_k</math> be the set of vertices adjacent to <math>i_1</math> in the dependency graph. Clearly <math>k-1\le d</math>. And it holds that
| |
| :<math>
| |
| \Pr\left[A_{i_1}\mid \bigwedge_{j=2}^m\overline{A_{i_j}}\right]
| |
| =\frac{\Pr\left[ A_i\wedge \bigwedge_{j=2}^k\overline{A_{i_j}}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right]}
| |
| {\Pr\left[\bigwedge_{j=2}^k\overline{A_{i_j}}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right]}
| |
| </math>,
| |
| which is due to the basic conditional probability identity
| |
| :<math>\Pr[A\mid BC]=\frac{\Pr[AB\mid C]}{\Pr[B\mid C]}</math>.
| |
| We bound the numerator
| |
| :<math>
| |
| \begin{align}
| |
| \Pr\left[ A_{i_1}\wedge \bigwedge_{j=2}^k\overline{A_{i_j}}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right]
| |
| &\le\Pr\left[ A_{i_1}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right]\\
| |
| &=\Pr[A_{i_1}]\\
| |
| &\le x_{i_1}\prod_{(i_1,j)\in E}(1-x_j).
| |
| \end{align}
| |
| </math>
| |
| The equation is due to the independence between <math>A_{i_1}</math> and <math>A_{i_k+1},\ldots,A_{i_m}</math>.
| |
| | |
| The denominator can be expanded using Lemma 1 as
| |
| :<math>
| |
| \Pr\left[\bigwedge_{j=2}^k\overline{A_{i_j}}\mid \bigwedge_{j=k+1}^m\overline{A_{i_j}}\right]
| |
| =\prod_{j=2}^k\Pr\left[\overline{A_{i_j}}\mid \bigwedge_{\ell=j+1}^m\overline{A_{i_\ell}}\right]
| |
| </math>
| |
| which by the induction hypothesis, is at least
| |
| :<math>
| |
| \prod_{j=2}^k(1-x_{i_j})=\prod_{\{i_1,i_j\}\in E}(1-x_j)
| |
| </math>
| |
| where <math>E</math> is the edge set of the dependency graph.
| |
| | |
| Therefore,
| |
| :<math>
| |
| \Pr\left[A_{i_1}\mid \bigwedge_{j=2}^m\overline{A_{i_j}}\right]
| |
| \le\frac{x_{i_1}\prod_{(i_1,j)\in E}(1-x_j)}{\prod_{\{i_1,i_j\}\in E}(1-x_j)}\le x_{i_1}.
| |
| </math>
| |
| Applying Lemma 1,
| |
| :<math>
| |
| \begin{align}
| |
| \Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]
| |
| &=\prod_{i=1}^n\Pr\left[\overline{A_i}\mid \bigwedge_{j=1}^{i-1}\overline{A_{j}}\right]\\
| |
| &=\prod_{i=1}^n\left(1-\Pr\left[A_i\mid \bigwedge_{j=1}^{i-1}\overline{A_{j}}\right]\right)\\
| |
| &\ge\prod_{i=1}^n\left(1-x_i\right).
| |
| \end{align}
| |
| </math>
| |
| }}
| |
| | |
| = Algorithmic Lovász Local Lemma =
| |
| We consider a restrictive case.
| |
| | |
| Let <math>X_1,X_2,\ldots,X_m\in\{\mathrm{true},\mathrm{false}\}</math> be a set of ''mutually independent'' random variables which assume boolean values. Each event <math>A_i</math> is an AND of at most <math>k</math> literals (<math>X_i</math> or <math>\neg X_i</math>). Let <math>v(A_i)</math> be the set of the <math>k</math> variables that <math>A_i</math> depends on. The probability that none of the bad events occurs is
| |
| :<math>
| |
| \Pr\left[\bigwedge_{i=1}^n \overline{A_i}\right].
| |
| </math>
| |
| In this particular model, the dependency graph <math>D=(V,E)</math> is defined as that <math>(i,j)\in E</math> iff <math>v(A_i)\cap v(A_j)\neq \emptyset</math>.
| |
| | |
| Observe that <math>\overline{A_i}</math> is a clause (OR of literals). Thus, <math>\bigwedge_{i=1}^n \overline{A_i}</math> is a '''<math>k</math>-CNF''', the CNF that each clause depends on <math>k</math> variables.
| |
| The probability
| |
| :<math>
| |
| \bigwedge_{i=1}^n \overline{A_i}>0
| |
| </math>
| |
| means that the the <math>k</math>-CNF <math>\bigwedge_{i=1}^n \overline{A_i}</math> is satisfiable.
| |
| | |
| The satisfiability of <math>k</math>-CNF is a hard problem. In particular, 3SAT (the satisfiability of 3-CNF) is the first '''NP-complete''' problem (the Cook-Levin theorem). Given the current suspect on '''NP''' vs '''P''', we do not expect to solve this problem generally.
| |
| | |
| However, the condition of the Lovasz local lemma has an extra assumption on the degree of dependency graph. In our model, this means that each clause shares variables with at most <math>d</math> other clauses. We call a <math>k</math>-CNF with this property a <math>k</math>-CNF with bounded degree <math>d</math>.
| |
| | |
| Therefore, proving the Lovasz local lemma on the restricted forms of events as described above, can be reduced to the following problem:
| |
| ;Problem
| |
| :Find a condition on <math>k</math> and <math>d</math>, such that any <math>k</math>-CNF with bounded degree <math>d</math> is satisfiable.
| |
| | |
| In 2009, Moser comes up with the following procedure solving the problem. He later generalizes the procedure to general forms of events. This not only gives a beautiful constructive proof to the Lovasz local lemma, but also provides an efficient randomized algorithm for finding a satisfiable assignment for a number of events with bounded dependencies.
| |
| | |
| Let <math>\phi</math> be a <math>k</math>-CNF of <math>n</math> clauses with bounded degree <math>d</math>, defined on variables <math>X_1,\ldots,X_m</math>. The following procedure find a satisfiable assignment for <math>\phi</math>.
| |
| | |
| {{Theorem
| |
| |Solve(<math>\phi</math>)|
| |
| :Pick a random assignment of <math>X_1,\ldots,X_m</math>.
| |
| :While there is an unsatisfied clause <math>C</math> in <math>\phi</math>
| |
| :: '''Fix'''(<math>C</math>).
| |
| }}
| |
| | |
| The sub-routine '''Fix''' is defined as follows:
| |
| {{Theorem
| |
| |Fix(<math>C</math>)|
| |
| :Replace the variables in <math>v(C)</math> with new random values.
| |
| :While there is unsatisfied clause <math>D</math> that <math>v(C)\cap v(D)\neq \emptyset</math>
| |
| :: '''Fix'''(<math>D</math>).
| |
| }}
| |
| | |
| The procedure looks very simple. It just recursively fixes the unsatisfied clauses by randomly replacing the assignment to the variables.
| |
| | |
| We then prove it works.
| |
| | |
| ===Number of top-level callings of Fix ===
| |
| In '''Solve'''(<math>\phi</math>), the subroutine '''Fix'''(<math>C</math>) is called. We now upper bound the number of times it is called (not including the recursive calls).
| |
| | |
| Assume '''Fix'''(<math>C</math>) always terminates.
| |
| :;Observation
| |
| ::Every clause that was satisfied before '''Fix'''(<math>C</math>) was called will still remain satisfied and <math>C</math> will also be satisfied after '''Fix'''(<math>C</math>) returns.
| |
| | |
| The observation can be proved by induction on the structure of recursion. Since there are <math>n</math> clauses, '''Solve'''(<math>\phi</math>) makes at most <math>n</math> calls to '''Fix'''.
| |
| | |
| We then prove that '''Fix'''(<math>C</math>) terminates.
| |
| | |
| === Termination of Fix ===
| |
| The idea of the proof is to '''reconstruct''' a random string.
| |
| | |
| Suppose that during the running of '''Solve'''(<math>\phi</math>), the '''Fix''' subroutine is called for <math>t</math> times (including all the recursive calls).
| |
| | |
| Let <math>s</math> be the sequence of the random bits used by '''Solve'''(<math>\phi</math>). It is easy to see that the length of <math>s</math> is <math>|s|=m+tk</math>, because the initial random assignment of <math>m</math> variables takes <math>m</math> bits, and each time of calling '''Fix''' takes <math>k</math> bits.
| |
| | |
| We then reconstruct <math>s</math> in an alternative way.
| |
| | |
| Recall that '''Solve'''(<math>\phi</math>) calls '''Fix'''(<math>C</math>) at top-level for at most <math>n</math> times. Each calling of '''Fix'''(<math>C</math>) defines a recursion tree, rooted at clause <math>C</math>, and each node corresponds to a clause (not necessarily distinct, since a clause might be fixed for several times). Therefore, the entire running history of '''Solve'''(<math>\phi</math>) can be described by at most <math>n</math> recursion trees.
| |
| | |
| :;Observation 1
| |
| ::Fix a <math>\phi</math>. The <math>n</math> recursion trees which capture the total running history of '''Solve'''(<math>\phi</math>) can be encoded in <math>n\log n+t(\log d+O(1))</math> bits.
| |
| Each root node corresponds to a clause. There are <math>n</math> clauses in <math>\phi</math>. The <math>n</math> root nodes can be represented in <math>n\log n</math> bits.
| |
| | |
| The smart part is how to encode the branches of the tree. Note that '''Fix'''(<math>C</math>) will call '''Fix'''(<math>D</math>) only for the <math>D</math> that shares variables with <math>C</math>. For a k-CNF with bounded degree <math>d</math>, each clause <math>C</math> can share variables with at most <math>d</math> many other clauses. Thus, each branch in the recursion tree can be represented in <math>\log d</math> bits. There are extra <math>O(1)</math> bits needed to denote whether the recursion ends. So totally <math>n\log n+t(\log d+O(1))</math> bits are sufficient to encode all <math>n</math> recursion trees.
| |
| | |
| :;Observation 2
| |
| ::The random sequence <math>s</math> can be encoded in <math>m+n\log n+t(\log d+O(1))</math> bits.
| |
| | |
| With <math>n\log n+t(\log d+O(1))</math> bits, the structure of all the recursion trees can be encoded. With extra <math>m</math> bits, the final assignment of the <math>m</math>
| |
| variables is stored.
| |
| | |
| We then observe that with these information, the sequence of the random bits <math>s</math> can be reconstructed from backwards from the final assignment.
| |
| | |
| The key step is that a clause <math>C</math> is only fixed when it is unsatisfied (obvious), and an unsatisfied clause <math>C</math> must have exact one assignment (a clause is OR of literals, thus has exact one unsatisfied assignment). Thus, each node in the recursion tree tells the <math>k</math> random bits in the random sequence <math>s</math> used in the call of the Fix corresponding to the node. Therefore, <math>s</math> can be reconstructed from the final assignment plus at most <math>n</math> recursion trees, which can be encoded in at most <math>m+n\log n+t(\log d+O(1))</math> bits.
| |
| | |
| The following theorem lies in the heart of the '''Kolmogorov complexity'''. The theorem states that random sequence is '''incompressible'''.
| |
| {{Theorem
| |
| |Theorem (Kolmogorov)|
| |
| :For any encoding scheme , with high probability, a random sequence <math>s</math> is encoded in at least <math>|s|</math> bits.
| |
| }}
| |
| | |
| Applying the theorem, we have that with high probability,
| |
| :<math>m+n\log n+t(\log d+O(1))\ge |s|=m+tk</math>.
| |
| Therefore,
| |
| :<math>
| |
| t(k-O(1)-\log d)\le n\log n.
| |
| </math>
| |
| In order to bound <math>t</math>, we need
| |
| :<math>k-O(1)-\log d>0</math>,
| |
| which hold for <math>d< 2^{k-\alpha}</math> for some constant <math>\alpha>0</math>. In fact, in this case, <math>t=O(n\log n)</math>, the running time of the procedure is bounded by a polynomial!
| |
| | |
| === Back to the local lemma ===
| |
| We showed that for <math>d<2^{k-O(1)}</math>, any <math>k</math>-CNF with bounded degree <math>d</math> is satisfiable, and the satisfied assignment can be found within polynomial time with high probability. Now we interprete this in a language of the local lemma.
| |
| | |
| Recall that the symmetric version of the local lemma:
| |
| {{Theorem
| |
| |Theorem (The local lemma: symmetric case)|
| |
| :Let <math>A_1,A_2,\ldots,A_n</math> be a set of events, and assume that the following hold: | |
| :#for all <math>1\le i\le n</math>, <math>\Pr[A_i]\le p</math>;
| |
| :#the maximum degree of the dependency graph for the events <math>A_1,A_2,\ldots,A_n</math> is <math>d</math>, and
| |
| :::<math>ep(d+1)\le 1</math>.
| |
| :Then
| |
| ::<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]>0</math>.
| |
| }}
| |
| Suppose the underlying probability space is a number of mutually independent uniform random boolean variables, and the evens <math>\overline{A_i}</math> are clauses defined on <math>k</math> variables. Then,
| |
| :<math>
| |
| p=2^{-k}
| |
| </math>
| |
| thus, the condition <math>ep(d+1)\le 1</math> means that
| |
| :<math>
| |
| d<2^{k}/e
| |
| </math>
| |
| which means the Moser's procedure is asymptotically optimal on the degree of dependency.
| |