Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There is a probability density function defined on the square [0,1]x[0,1].

The pdf is finite, i.e., the cumulative density is positive only for pieces with positive area.

Now Alice and Bob play a game: Alice marks two disjoint squares, Bob chooses the square that contains the maximum probability, and Alice gets the other square. The goal of Alice is to maximize the probability in her square.

Obviously, in some cases Alice can assure herself a probability of 1/2, for example, if the pdf is uniform in [0,$1 \over 2$]x[0,1], she can cut the squares [0,$1 \over 2$]x[0,$1 \over 2$] and [0,$1 \over 2$]x[$1 \over 2$,1], both of which contain $1 \over 2$.

However, in other cases Alice can assure herself only $1 \over 4$, for example, if the pdf is uniform in [0,1]x[0,1].

Are there pdfs for which Alice cannot assure herself even $1 \over 4$ ?

What is the worst case for Alice?

share|improve this question
    
Are the squares allowed to touch at the edges-that is only the interiors need to be disjoint? –  Ross Millikan May 10 '13 at 22:14
    
I think this does not matter, because the cumulative density of the edges is 0. –  Erel Segal Halevi May 11 '13 at 17:54
    
This answer, math.stackexchange.com/a/408666/29780 , implies that, if there are (n-1) Bobs, then Alice can assure herself at most 1/(2n) of the cake. This is interesting, because, if we don't limit ourselves to square pieces, Alice can always assure herself 1/n of the cake. –  Erel Segal Halevi Jun 1 '13 at 18:45
add comment

2 Answers

up vote 1 down vote accepted

I think Alice can always assure herself at least $1 \over 4$ cdf, in the following way.

First, in each of the 4 corners, mark a square that contains $1 \over 4$ cdf. Since the pdf is finite, it is always possible to construct such a square, by starting from the corner and increasing the square gradually, until it contains exactly $1 \over 4$ cdf.

There is at least one corner, in which the side length of such a square will be at most $1 \over 2$ . Suppose this is the lower-left corner, and the side length is a, so square #1 is [0,a]x[0,a], with a <= $1 \over 2$.

Now, consider the following 3 squares:

  • To the right of square #1: [a,1]x[0,1-a]
  • On top of square #1: [0,1-a]x[a,1]
  • On the top-right of square #1: [a,1]x[a,1]

The union of these squares covers the entire remainder after we remove square #1. This remainder contains $3 \over 4$ cdf. So, the sum of cdf in all 3 squares is at least $3 \over 4$ (probably more, because the squares overlap).

Among those 3, select the one with the greatest cdf. It must contain at least $1 \over 3$ of $3 \over 4$, i.e., at least $1 \over 4$. This is square #2.

So, Alice can always cut two squares that contain at least $1 \over 4$ cdf.

Note that this procedure relies on the fact (that I mentioned in the original question) that the pdf is finite. Otherwise, it may not always be possible to construct a square with $1 \over 4$ cdf.

share|improve this answer
add comment

I assume by disjoint squares you mean squares made with 2 cuts, each parallel to an axis and that the leftover rectangles are thrown away.

A PDF uniform on $x$ when $y=y_0$ and 0 otherwise would give Alice nothing.

In light of @RossMillikan comment

$$P(x,y)=\begin{cases} \frac{1}{5}&[0,0],[1,0],[0,1],[1,1],[\frac{1}{4},\frac{1}{4}]\\ 0&\text{otherwise} \end{cases}$$

share|improve this answer
    
OP just said two disjoint squares,so here Alice could cut $[0,\frac 12] \times [y_0-\frac 14,y_0+\frac 14]$ and $[\frac 12,1] \times [y_0-\frac 14,y_0+\frac 14]$ –  Ross Millikan May 10 '13 at 22:12
    
+1 Well done...... –  Ross Millikan May 11 '13 at 0:15
1  
The problem says, "the cumulative density is positive only for pieces with positive area." I understood that to mean that single points have probability zero. –  Gerry Myerson May 11 '13 at 0:26
    
@GerryMyerson The function does not have to be degenerate. A continuous function of sufficient "peakiness" will do. This can be thought of as a limiting case. –  Dale M May 11 '13 at 1:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.