# A Tutorial on Various Aspects of Mixing

N/A
N/A
Protected

Share "A Tutorial on Various Aspects of Mixing"

Copied!
53
0
0

Full text

(1)

## A Tutorial on Various Aspects of Mixing

School of Mathematics & School of Computer Science Georgia Institute of Technology

January 9, 2009

1/42

(2)

Acknowledgement

The part Colorings on Trees of this presentation was given to me by Juan Vera. The part on Broadcasting on a Tree was given by Nayantara Bhatnagar. I am grateful for their help.

(3)

## Catalan Shuffling: an open question

Consider the setCn of triangulations of a convexn-sided polygon, for integern≥4.

Well-known: |Cn|= [1/(n+ 1)] 2nn

, thenth Catalan number.

I A shuffle consists of picking one of then−3 diagonals uniformly at random and “flipping the diagonal”–

removing the diagonal and in the quadrilateral created by this removal, placing the (only possible) other diagonal.

I How long until the triangulation is random?

I Conjecture (Aldous). O(n3/2) shuffles ought to be enough!,

I Best known. Lower bound : Ω(n3/2) (Mol-Ree-Ste ’99) Upper bound ofO(n4(logn)) (McS–T. ’99).

3/42

(4)

## Catalan Shuffling: an open question

Consider the setCn of triangulations of a convexn-sided polygon, for integern≥4.

Well-known: |Cn|= [1/(n+ 1)] 2nn

, thenth Catalan number.

I A shuffle consists of picking one of then−3 diagonals uniformly at random and “flipping the diagonal”–

removing the diagonal and in the quadrilateral created by this removal, placing the (only possible) other diagonal.

I How long until the triangulation is random?

I Conjecture (Aldous). O(n3/2) shuffles ought to be enough!,

I Best known. Lower bound : Ω(n3/2) (Mol-Ree-Ste ’99) Upper bound ofO(n4(logn)) (McS–T. ’99).

(5)

## Catalan Shuffling: an open question

Consider the setCn of triangulations of a convexn-sided polygon, for integern≥4.

Well-known: |Cn|= [1/(n+ 1)] 2nn

, thenth Catalan number.

I A shuffle consists of picking one of then−3 diagonals uniformly at random and “flipping the diagonal”–

removing the diagonal and in the quadrilateral created by this removal, placing the (only possible) other diagonal.

I How long until the triangulation israndom?

I Conjecture (Aldous). O(n3/2) shuffles ought to be enough!,

I Best known. Lower bound : Ω(n3/2) (Mol-Ree-Ste ’99) Upper bound ofO(n4(logn)) (McS–T. ’99).

3/42

(6)

## Catalan Shuffling: an open question

Consider the setCn of triangulations of a convexn-sided polygon, for integern≥4.

Well-known: |Cn|= [1/(n+ 1)] 2nn

, thenth Catalan number.

I A shuffle consists of picking one of then−3 diagonals uniformly at random and “flipping the diagonal”–

removing the diagonal and in the quadrilateral created by this removal, placing the (only possible) other diagonal.

I How long until the triangulation israndom?

I Conjecture(Aldous). O(n3/2) shuffles ought to be enough!,

I Best known. Lower bound : Ω(n3/2) (Mol-Ree-Ste ’99) Upper bound ofO(n4(logn)) (McS–T. ’99).

(7)

## Catalan Shuffling: an open question

Consider the setCn of triangulations of a convexn-sided polygon, for integern≥4.

Well-known: |Cn|= [1/(n+ 1)] 2nn

, thenth Catalan number.

I A shuffle consists of picking one of then−3 diagonals uniformly at random and “flipping the diagonal”–

removing the diagonal and in the quadrilateral created by this removal, placing the (only possible) other diagonal.

I How long until the triangulation israndom?

I Conjecture(Aldous). O(n3/2) shuffles ought to be enough!,

I Best known. Lower bound : Ω(n3/2) (Mol-Ree-Ste ’99) Upper bound ofO(n4(logn)) (McS–T. ’99).

3/42

(8)

## The rho (nonreversible) walk – recently settled question

Consider thesimple random walkon the discrete circle Zp (for p: prime) – move fromatoa±1, with equal probability.

Well-known: O(n2) steps to get to a randomi∈ {0,1, . . . , p}.

I Add a doublingmove – from atoa±1 or 2a, with probability 1/3 independently.

I Now how long until random?

Theorem(Kim-Mon–T. ’07). O(logn log logn) moves sufficient. Motivation: Arises in the analysis of Pollard’s Rho algorithm for finding thediscrete logarithm in a cyclic group of prime order.

(9)

## The rho (nonreversible) walk – recently settled question

Consider thesimple random walkon the discrete circle Zp (for p: prime) – move fromatoa±1, with equal probability.

Well-known: O(n2) steps to get to a randomi∈ {0,1, . . . , p}.

I Add a doublingmove – from atoa±1 or 2a, with probability 1/3 independently.

I Now how long until random?

Theorem(Kim-Mon–T. ’07). O(logn log logn) moves sufficient. Motivation: Arises in the analysis of Pollard’s Rho algorithm for finding thediscrete logarithm in a cyclic group of prime order.

4/42

(10)

## The rho (nonreversible) walk – recently settled question

Consider thesimple random walkon the discrete circle Zp (for p: prime) – move fromatoa±1, with equal probability.

Well-known: O(n2) steps to get to a randomi∈ {0,1, . . . , p}.

I Add a doublingmove – from atoa±1 or 2a, with probability 1/3 independently.

I Now how long until random?

Theorem(Kim-Mon–T. ’07). O(logn log logn) moves sufficient. Motivation: Arises in the analysis of Pollard’s Rho algorithm for finding thediscrete logarithm in a cyclic group of prime order.

(11)

## The rho (nonreversible) walk – recently settled question

Consider thesimple random walkon the discrete circle Zp (for p: prime) – move fromatoa±1, with equal probability.

Well-known: O(n2) steps to get to a randomi∈ {0,1, . . . , p}.

I Add a doublingmove – from atoa±1 or 2a, with probability 1/3 independently.

I Now how long until random?

Theorem(Kim-Mon–T. ’07). O(logn log logn) moves sufficient.

Motivation: Arises in the analysis of Pollard’s Rho algorithm for finding thediscrete logarithm in a cyclic group of prime order.

4/42

(12)

## The rho (nonreversible) walk – recently settled question

Consider thesimple random walkon the discrete circle Zp (for p: prime) – move fromatoa±1, with equal probability.

Well-known: O(n2) steps to get to a randomi∈ {0,1, . . . , p}.

I Add a doublingmove – from atoa±1 or 2a, with probability 1/3 independently.

I Now how long until random?

Theorem(Kim-Mon–T. ’07). O(logn log logn) moves sufficient.

Motivation: Arises in the analysis of Pollard’s Rho algorithm for finding thediscrete logarithm in a cyclic group of prime order.

(13)

## Welcome to Markov Chains

Let (Ω, P, π) : denote a Markov chain on state space Ω, with the transition probab. matrixP, and (unique) invariant measureπ:

P(x, y)≥0,∀x, y∈Ω and X

y

P(x, y) = 1,∀x∈Ω,

X

x∈Ω

π(x)P(x, y) =π(y), ∀y∈Ω.

I Always assumeirreducible, withπ having full support on Ω.

I Typically assume aperiodic, soPn(x,·)→π(·), as n→ ∞.

I Often have reversibility :

π(x)P(x, y) =π(y)P(y, x), ∀x, y∈Ω.

5/42

(14)

Markov Chain Monte Carlo

Typically given a LARGE set Ω, the goal is to sample elements from Ω at random from a desired distributionπ over Ω.

Usuallyπ is given implicitly.

Examples: weighted matchings, uniform independent sets, colorings etc. of a given graph.

The MCMC approach to sampling is to construct a Markov chain (based on “local” moves) on Ω which converges toπ.

I Start at any x0 ∈Ω; run the chain for T steps, and output xT.

I key question: How large doesT have to be so that the distribution of xT is a good approximation toπ?

(15)

## Some Successes

Defn. Fully poly. randomized approx. scheme(FPRAS): Given inputx, error parameter >0, and a confidence parameter δ >0, an approximation algorithm outputting A(x) (for the true valuef(x)), so that

Pr

(1−)f(x)≤A(x)≤(1 +)f(x)

≥1−δ , in time polynomial in|x|,−1 and log(1/δ).

Some examples having an FPRAS using the MCMC approach:

I Counting Matchings in General Graphs, Perfect Matchings in Bipartite Graphs, Computing the permanent of a matrix

I Counting the number of linear extensions of a poset

I Computing the volume of an n-dim. convex body

7/42

(16)

## Some Frustrations

Some notorious open problems:

I Generating perfectmatchings u.a.r. from a general G.

I Generating acyclic orientations of Gu.a.r. from a given undirected graph G

I Contingency Table Problems: given row and column sums, generate u.a.r. a table of nonneg. integers with those sums

I Is the basis-exchange walk on bases of an arbitrary matroid rapidly mixing? (known for spanning trees, and balanced matroids [F-M ’9?])

I Generating independent sets from a given bipartitegraph

(17)

## Many Paths to Mixing – Distance to Equilibrium

Letknx(y) =Pn(x, y)/π(y) density w.r.t. π at time n≥0, so under aperiodicity,kxn(y)→1.

Defn. Lp-distance:

kkn−1kpp,π =P

y∈Ω|kn(y)−1|pπ(y), 1≤p <+∞.

Forµ: probab. distribution on Ω,

I p= 1:

kµ−πktv= 1 2

X

y

|µ(y)−π(y)|= 1

2kµ/π−1k1,π,

I p= 2:

Varπ(µ/π) =X

y

µ(y) π(y)−1

2

π(y) =kµ/π−1k22,π. Defn. Rel. Entropy:

D(Pn(x,·)kπ) =P

yPn(x, y) logPn(x, y)/π(y)= Entπ(knx), where Entπ(f) = EπflogfEπflog(Eπf).

9/42

(18)

Various Mixing Times

A Key Question. Howquicklydoes it converge to 1?

The total variation, relative entropy andL2 mixing times are defined as follows, (using worst-case starting point).

τ() = min{n:∀x∈Ω, kPn(x,·)−πktv≤} τD() = min{n:∀x∈Ω, D(Pn(x,·)kπ)≤} τ2() = min{n:∀x∈Ω, kkn(x,·)−1k2,π≤}

I

(19)

## List of Techniques

Functional Analytic,IsoperimetricApproaches:

I Spectral Gap,Conductance (Cheeger-type constants)

I Entropy Constant (Dai Pra-Paganoni-Posta, Gao-Quastel, Bobkov-T.), Log-Sobolev Constant (Gross, Bakry-Emery, Diaconis-Saloff-Coste, Miclo, ...)

I Spectral Profile (Goel-Montenegro-T.) and Isoperimetric Profile(Kannan-Lovasz) ProbabilisticApproaches:

I Coupling, Path coupling (Bubley-Dyer),

Coupling From the Past (Propp-Wilson), Evolving Sets (Morris-Peres)

Other Techniques

I Decomposition and Comparison

11/42

(20)

## Treatment with Dirichlet Forms

The following will be done on the white board:

I Motivating definitions of spectral gap, entropy constant, ...

I Comparison of Dirichlet Forms

(21)

An Amazing Conjecture

[Due to Aldous-Diaconis ’92].

Conjecture. For everyG,λIP(G) =λRW(G).

IP: Start withnlabeled particles on ann-vertex graph. For each edgeij independently and at rate 1, interchangethe particlesiand j. (This is reversible w.r.t. uniform distribution onn! configurations. of particles.)

RW: Observe a single particle above, thus obtaining a (continuous) time simple random walk onG.

I Known to hold for G=Cn, Kn, Trees, and a bit more ...

I Asymptotically forG:d-dimensional grid of side length n.

13/42

(22)

## The logarithmic factor: some examples

I Entropy Constant vs Log-Sobolev constant:

random transpositions, k-sets of an n-set

I The Pollard Rho walk

I The Thorp shuffle

(23)

Coupling

Colorings on graphs : a case study

Refer to the file coloring.pdf, which covers Jerrum’s coupling and a bit more.

15/42

(24)

## Next Topic

Temporal vs SpatialMixing

(25)

Temporal Mixing and Uniqueness of Gibbs

Typically one expects fast mixing of Glauber (and other local) dynamics in the uniqueness regime, and (exponentially) slow mixing in the non-uniqueness regime:

Examples include: OnZd,

Ising at low-temperature (largeβ >0), Hard-core lattice gas (i.e., weighted independent sets), etc.

However, Glauber dynamics onZdin the multiphase region is still poorly understood: F. Martinelli’s problem with the +boundary condition onZ2.

17/42

(26)

## An Amazing Theorem

[Martinelli-Olivieri-Schonman’94].

For the Ising model on a finite box of sizeninZ2, the Glauber dynamics satisfies:

I If T > Tc, then mixing time =O(nlogn)

I If T < Tc, then mixing time = exp(Ω(√ n)).

(27)

A notion of Strong Spatial Mixing

Defn. A system hasSSMif∃ constantsβ and α >0, such that for any two subsets Λ,Ψ, with Λ⊂Ψ, any site u∈∂Ψ, and any pair of bdry configs. τ andτu differing only atu,

d µτΨ, µτΨu

|Λ≤β|Λ|exp(−α dist(u,Λ)).

I Weak Spatial Mixing: replaced(u,Λ) by d(∂Ψ,Λ); holds up to (and corresponds to) uniqueness of Gibbs etc.

19/42

(28)

## Optimal Temporal Mixing

[In words: Glauber dynamics on a finite volume Ψwith ANY bdry config. reaches stationarity in timeO(nlogn), n=|Ψ|.]

Defn. Glauber has OTM if∃ const. b, c >0 such that

∀Ψ⊂⊂ Zd with any bdry config. for any two instances (Xt) and (Yt) of the chain, anyk∈ Z+,

d(Xkn, Ykn)≤bn e−ck.

I e.g., if entropy constantρ0≥c0/n, then OTM holds.

Thm. [Stroock-Zegarlinski’92]. For spin systems onZd, with nearest neighbor interactinos, OTM holds iff SSM holds.

(29)

## Path of Disagreement in Bdd-degree Graphs

Key Lemma[Zegarlinski’ ??, van den Berg’93] (DSVW’02):

G= (V, E), |V|=n, max degree ∆.

LetA, B⊂V arbitrary with r= dist(A, B).

Xt, Yt : two copies of Glauber on GwithX0≡Y0 off ofA.

Then for pos. integerk≤r/[(∆−1)e2], if we run for T =kn steps, we have

P(XT(B)6=Yt(B))≤4 min{|A|,|B|}(∆−1)ek r

r

. The probability is under “identity coupling” of (Xt),(Yt).

I Cor. IfT =kn,r= dist(A, B)≥(∆−1)e2k, P(XT(b)6=YT(B))≤4|A|e−dist(A,B). WMA assumed above that|A| ≤ |B|.

21/42

(30)

## OTM implies SSM in Z

d

Run chain (Xt) with the stat. measureµτΨ, and chain (Yt) with the stat. measureµτΨu, starting withX0=Y0 (in the same configuration of spins).

Stop at timet= (2d−1)edist(u,Λ)2 n(say). Then

I

d(µτΨ, µτΨu)≤d(µτΨ, Xt) +d(Xt, Yt) +d(µτΨu, Yt).

I

d(Xt, Yt)|Λ≤4|Λ|e−dist(u,Λ), sincedisagreement has not percolated!

I OTOH,

d(µτΨ, Xt)|Λ≤b0|Λ|exp

− c0

(2d−1)e2 dist(u,Λ) , due to OTM.

(31)

OTM implies SSM in Z

d

Run chain (Xt) with the stat. measureµτΨ, and chain (Yt) with the stat. measureµτΨu, starting withX0=Y0 (in the same configuration of spins).

Stop at timet= (2d−1)edist(u,Λ)2 n(say). Then

I

d(µτΨ, µτΨu)≤d(µτΨ, Xt) +d(Xt, Yt) +d(µτΨu, Yt).

I

d(Xt, Yt)|Λ≤4|Λ|e−dist(u,Λ), sincedisagreement has not percolated!

I OTOH,

d(µτΨ, Xt)|Λ≤b0|Λ|exp

− c0

(2d−1)e2 dist(u,Λ) , due to OTM.

22/42

(32)

## OTM implies SSM in Z

d

Run chain (Xt) with the stat. measureµτΨ, and chain (Yt) with the stat. measureµτΨu, starting withX0=Y0 (in the same configuration of spins).

Stop at timet= (2d−1)edist(u,Λ)2 n(say). Then

I

d(µτΨ, µτΨu)≤d(µτΨ, Xt) +d(Xt, Yt) +d(µτΨu, Yt).

I

d(Xt, Yt)|Λ≤4|Λ|e−dist(u,Λ), sincedisagreement has not percolated!

I OTOH,

d(µτΨ, Xt)|Λ≤b0|Λ|exp

− c0

(2d−1)e2 dist(u,Λ)

, due to OTM.

(33)

Proof Sketch of Key Lemma

Observe: if sitev at timeT has different spins, then there must exist a path of disagreement fromA tov: i.e., ∃ path

v0, v1, . . . , vl=v and 0< t1 < t2· · ·< tl≤T, s.t. v0 ∈A, and vi updated at timeti.

I Pr[v0, . . . , vl]≤ Tl

(1/n)l,for a fixed path.

I No. of paths of lengthl≥r fromA toB is at most min{|A|,|B|}∆(∆−1)l−1.

I So Pr(Xkn(B)6=Ykn(B))≤ |A|

(∆−1)

P

l≥r

(∆−1)ek

l

l

≤4|A|(∆−1)ek

r

r

,

≤4|A|e−r, ifr ≥(∆−1)e2k.

23/42

(34)

## But ... what about the sub-exponential growth?

Have we used the fact that we were inZd?

I In the OTM bound, we really should have used a bound of d(µτΨ, Xt)|Λ≤b0|Ψ|exp

− c0

(2d−1)e2 dist(u,Λ) , rather than the smaller bound with |Λ|in place of|Ψ|, since the chain was run on Ψ rather than on Λ.

I So to justify the “fudge” we actually need an extra lemma:

this would argue that we could first restrict our attention to dynamics inside a volume Λk which contains all sites within distance ˆk= (2d−1)e2k from some site in Λ.

I The choice of ˆk still lets us use the path of diagreement argument on not reachingΛ.

(35)

## Fudge contd...

I The above would then give a bound of |Λk|e−c

0dist(u,Λ) (2d−1)e2

(plus another exponential term such as, e−ck|Λk|, for the probability of missing Λk, while choosing sites at random from Ψ: using Chernoff’s bound, e.g.)

I Now crucially, the “sub-exponential growth” of Zd can be used in saying |Λk| ≤

2[2d−1]e2kd

|Λ|and absorbing it into :

k|e−c0···≤ |Λ|e−c

00 dist(u,Λ) (2d−1)e2 .

Details in [Dyer-Sinclair-Vigoda-Weitz’02].

25/42

(36)

## Spectral Gap and Correlations on a general graph

At∞ temperature, where distinct vertices are independent, the Glauber dynamics on a graph ofnvertices reduces to an

(accelerated by a factor ofn) random walk on a discrete n-cube where the relaxation is Θ(1).

The next result shows that at any temperature where such fast relaxation takes place, a fairly strong form of independence holds. The setting is that of any graph ofbounded degree.

(37)

Spectral Gap and Correlations – 2

Thm. [Ber-Ken-Mos-Per’05] LetGbe bdd. degree graph, and letσr be config. on the setGr of all vertices at distance r from a fixed vertexv. Let therelaxation timeof Glauber dynamics onGr satisfyτ2(Gr) =O(1). Then the Gibbs distribution on Gr has the following property:

For any fixed setA of vertices,∃cA>0, s.t. for r large enough, Cov[f, g]≤e−cArp

Var(f)Var(g),

providedf(σ) depends only onσA andg(σ) depends only onσr. (Equivalently,∃c0A>0 s.t. the mut. inform. I(σA, σr)≤e−c0Ar.)

I Proof uses disagreement percolation and coupling as before.

I Thm could hold also when there are multiple Gibbs measures– e.g., the Ising model in the “intermediate regime” – for 1−2≤1/√

b, one gets limr→∞I[σ0, σr] = 0.

27/42

(38)

## An Open Question

Question[BKMP’05]:

For the Ising model (with free boundary conditions and no external field) on a general graph of bounded degree, does the converse of the above theoremhold?

That is, does uniform exponential decay of point-to-set correlations imply a uniform spectral gap?

I F.M. : Not always true – fails in certain lattices if plus bdry conditions are allowed.

(39)

## Broadcast Process on a Tree

Model

I T infinite rooted tree where each node has ∆ children.

I k colors,σv ∈[k] is the color at vertexv.

I Choose σr at the root uniformly at random.

I Independent Markov chain on each edge (u, v). P(i, j) = P[σu=j|σv=i]

I Proper colorings.

P(i, j) = δi6=j k1

29/42

(40)

Model

I T infinite rooted tree where each node has ∆ children.

I k colors,σv ∈[k] is the color at vertexv.

I Choose σr at the root uniformly at random.

I Independent Markov chain on each edge (u, v).

P(i, j) = P[σu=j|σv=i]

I Proper colorings.

P(i, j) = δi6=j k1

(41)

30/42

(42)

(43)

32/42

(44)

(45)

34/42

(46)

(47)

36/42

(48)

Reconstruction

How doesµ(·|X) behave as a function of a typical coloringX?

∃c, lim

`→∞EX(|µ(c|X)− 1 k|)>0

(49)

Applications I -Phylogeny

I [Mossel ’04], [Daskalakis-Mossel-Roch ’06 ] Evolution of DNA, phylogenetic reconstruction.

38/42

(50)

Applications II - Convergence of Markov Chains

I [Kenyon-Mossel-Peres ’01], [Berger-K-M-P ’05]

O(n) relaxation time for Glauber dynamics on bounded degree graphs implies non-reconstruction.

I [Martinelli-Sinclair-Weitz ’03] Exponential decay of correlation on the tree impliesO(nlnn) convergence for Glauber dynamics when “uniqueness” holds.

(51)

## Applications III - Replica Symmetry Breaking Transition

I [Achlioptas, Coja-Oghlan ’08]

(1/2 +o(1))∆/ln ∆< kd<(1−o(1))∆/ln ∆.

I Conjecture that kd is the same as the reconstruction threshold for trees. There is very recent work in this direction by [Montanari-Restrepo-T.]

40/42

(52)

Bounds on the Threshold for Non-reconstruction

I [Brightwell-Winkler’00]

Non-Reconstruction fork≥∆ + 1

I [Jonasson’02]

fork≥∆ + 1: root is unbiased for any fixed coloringof the leaves; (thus the Gibbs measure is unique.)

I [Mossel-Peres ’03]

Reconstruction when k≤ (1−ε)∆ln ∆ .

I [B-Vera-Vigoda-Weitz ’08]

Non-reconstruction for k > (1+ε)∆ln ∆ for ∆≥∆ε.

I [Sly ’08]

Non-reconstruction for ∆≤k(lnk+ ln lnk+ 1 +o(1)).

Reconstruction for ∆≥k(lnk+ ln lnk+ 1−ln 2−o(1)).

(53)

## Bounds on Mixing

I [Bhatnagar-Vera-Vigoda-Weitz ’08]

O(nlogn) mixing for a certain Block dynamics, by bounding the entropy constant of the dynamics for k > (1+ε)∆ln ∆ for ∆≥∆ε.

I [Goldberg-Jerrum-Karpinsky ’08]

Glauber: For fixed kand ∆ so that 3≤k≤∆/2 log(∆):

Upper bound ofnO(∆/log ∆) and a lower bound of nΩ(∆/klog ∆).

Problem 1. More precise bounds on the performance of Glauber “around”k= ∆/log ∆ ,especially in the range

∆/2 log ∆< k <2∆/log ∆ . Problem 2. SSM for k≥∆ + 1.

42/42

References

Related documents

§3, the effects of applied perturbation on charge imbalance created due to deviation in the effective charge as well as in distribution function of quasiparticles from their

The aim of this study was to compare the efficacy of 3 different methods namely E Test, ORSAB method, and disc diffusion method with Oxacillin and Cefoxitin

Microbial degradation of toxic substances is one of the important growth areas of applied microbiology. It is well known that successful removal of any pollutant through

www.ijnglt.com Page 2 The increasing use of the Internet for information has created a feeling among some library professionals and members of the public that

Moreover, this 4 limit handling procedure can be used with any other constant matrix load flow methods.An analytical investigation based on the iteration functions for various

When TLC showed disappearance of starting material, cold water (50mL) was added to the reaction mixture and extracted with ether (2x50mL). Solvent removal and purification afforded

7.4.3.5. Attempted Synthesis of 13a. The progress of the reaction was monitored by TLC. Removal of the solvent gave an amorphous residue, which was chromatographed on silica. Elution

In the power system the inter harmonics are created by harmonic current of the inverter when it will going to propagate through the dc link.. This topic is a case study of the