A child is presented with n boxes, one after another. Upon receiving

a box, the child must decide whether or not to open it. If the child

does not open a box, he is never allowed to revisit it. Half the boxes

have presents in them, but the decision about which boxes have

presents is made by an omniscient and malicious Santa who wants the

child to open as many empty boxes as possible before finding a

present.

Devise and analyze a randomized algorithm for the child which

minimizes the expected number of boxes that need to be opened before

the child finds the first present. Assume Santa knows your algorithm,

Note: This problem has applications to wireless networks: basically

boxes are time-steps, Santa is a jamming adversary, and opening a box

means spending energy to listen in a time-step.

Our problem has the following setup:

• $n$ boxes

• $\frac{n}{2}$ boxes have presents

• Birthday paradox tells us that we need $\sqrt{n}$ pebbles to fit expect a “collision” in $n$ bins.

If we naively pick boxes in order, santa will obviously put the boxes in the last half of our ’box array’. if this is true, we will have to pick $\frac{n}{2} + 1 = O(n)$ boxes to get a gift.

Randomization helps us greatly here as Santa cannot account for our random choices, though his placements will probably not be random. If we divide the array in half we can find a lower bound than $O(n)$ for our number of opened boxes. As the birthday paradox was discussed in class, we can expect that given n bins and p pebbles tossed randomly into bins, $\sqrt{ n }$ tosses gives us an expectation of 1 “collision” or two pebbles going into the same bin. If we think of our pick of a box as a pebble and santa’s placement of a box as a pebble, a “collision” is us picking a box with a gift.

If we split the array in half and choose $\sqrt{ n } + \epsilon$ (where $\epsilon$ is some arbitrary constant) boxes from the first subarray, we would expect a collision if there were at a handful of gift s in the first array. If we do not get a gift, we know that there are likely to be more gifts in the second have of the array, and as such, we can start choosing linearly from that array. Even if santa loads the back half of the array with gifts, we are still going to be picking $O(\sqrt{n+\epsilon} + C) = O(\sqrt{n+\epsilon})$.

Written by Aaron Gonzales

I'm a typically atypical guy.

Updated