Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Are the min max is equivalent to max min?

  1. Jun 1, 2012 #1
    Hello,

    Is

    [tex]\underset{i}{\min}\underset{n}{\max}=\underset{n}{\max}\underset{i}{\min}[/tex]?

    Thanks
     
  2. jcsd
  3. Jun 1, 2012 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    No. Take

    [tex]x_{i,n}=\left\{\begin{array}{l} 0 ~\text{if}~i+n~\text{even}\\
    1 ~\text{if}~i+n~\text{odd}\end{array}\right.[/tex]
     
  4. Jun 1, 2012 #3
    Yeah, right.
     
  5. Jun 1, 2012 #4
    In general you do not have equality between min-max and max-min, however I couldn't resist mentioning a very neat inequality I learned a bit ago.

    Given a real valued function ##P(x,y): X \times Y \rightarrow \mathbb{R}## one has

    $$\inf_{x\in X} \sup_{y\in Y} P(x,y) \geq \sup_{y\in Y} \inf_{x\in X} P(x,y)$$

    If you aren't familiar with sup (supremum - least upper bound) and inf (infimum - greatest lower bound) you can think of sup as max and inf as min.

    I learned this from Robert McCann, it's in the following article. Skip to 2.2 Game Theory for an intuitive 'proof'.
    http://www.math.toronto.edu/mccann/papers/FiveLectures.pdf
     
  6. Jun 2, 2012 #5
    Is this inequality true in general?
     
  7. Jun 2, 2012 #6
    Yes. To see this pick [itex]x'\in X[/itex] and [itex]y'\in Y[/itex]. Clearly [itex]\sup_Y P(x',y)\geq \inf_X P(x,y')[/itex], and since this is true for all [itex]y'\in Y[/itex] we have [itex]\sup_Y P(x',y)\geq \sup_Y \inf_X P(x,y)[/itex], by definition of the supremum. Similarly, since this is true for all [itex]x'\in X[/itex] we have [itex]\inf_X\sup_Y P(x,y)\geq \sup_Y \inf_X P(x,y)[/itex] by definition of the infimum.
     
    Last edited: Jun 2, 2012
  8. Jun 2, 2012 #7
    OK, what abou max max or min min, are they interchangeable?
     
  9. Jun 2, 2012 #8
    Yes. Consider [itex]\sup_X\sup_Y P(x,y)[/itex]. By definition we have [itex]\sup_X\sup_Y P(x,y)\geq P(x',y')[/itex] for all [itex]x'\in X,y'\in Y[/itex], so [itex]\sup_X\sup_Y P(x,y)\geq \sup_{X\times Y} P(x,y)[/itex] by definition of [itex]\sup[/itex]. Conversely, if [itex]\sup_X\sup_Y P(x,y)\not\leq \sup_{X\times Y} P(x,y)[/itex] then there is [itex]x'\in X[/itex] with [itex]\sup_Y P(x',y)\not\leq \sup_{X\times Y} P(x,y)[/itex], and thus there is [itex]y'\in Y[/itex] with [itex]\sup_Y P(x',y')\not\leq \sup_{X\times Y} P(x,y)[/itex], which would be a contradiction. So [itex]\sup_X\sup_Y P(x,y)= \sup_{X\times Y} P(x,y)[/itex] and a symmetry argument gives [itex]\sup_X\sup_Y P(x,y)= \sup_{X\times Y} P(x,y)=\sup_Y\sup_X P(x,y)[/itex].

    Edit: We require that the suprema and infima are defined, I forgot to mention that in my original response.
     
  10. Jun 2, 2012 #9
    Yes, of course they are defined.

    Thanks
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Are the min max is equivalent to max min?
  1. Max min trig functions (Replies: 5)

Loading...