probable squares in a square cake

Question

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?

Answer 1

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.

Answer 2

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}$$