patternMinor
What is the best you can do with a noisy message?
Viewed 0 times
cantheyouwhatwithmessagenoisybest
Problem
You play a TV game in which you have to open one door out of $n$. Behind each door, there is a treasure with probability 1/2, independent of the other doors, so your apriori chance of winning is 1/2.
In order to increase your chances, you can coordinate with a friend. You do the coordination before the game starts. Then, the friend can see what's behind all the doors, and send you a single integer number between 1 and $n$.
You receive your friend's number, but, in addition to that number, you receive $k-1$ more numbers between 1 and $n$, which are selected at random without replacement between 1 and $n$. You don't know which of the $k$ numbers is the real message and which is fake.
What strategy can you and your friend can coordinate, such that your probability of finding a treasure is maximized?
EXAMPLE: suppose $k=2$. Then, one possible strategy is that the friend just selects a door with a treasure behind it, and sends its number to you. You receive your friend's number and another number, in random order. Suppose you just pick the first number that you receive and open the door with that number. If it is your friend's number then you win; if this is a fake number then you have a chance of 1/2 to win. Hence, your total chance of winning with this strategy is 3/4. Is this correct? Is there a better strategy?
In order to increase your chances, you can coordinate with a friend. You do the coordination before the game starts. Then, the friend can see what's behind all the doors, and send you a single integer number between 1 and $n$.
You receive your friend's number, but, in addition to that number, you receive $k-1$ more numbers between 1 and $n$, which are selected at random without replacement between 1 and $n$. You don't know which of the $k$ numbers is the real message and which is fake.
What strategy can you and your friend can coordinate, such that your probability of finding a treasure is maximized?
EXAMPLE: suppose $k=2$. Then, one possible strategy is that the friend just selects a door with a treasure behind it, and sends its number to you. You receive your friend's number and another number, in random order. Suppose you just pick the first number that you receive and open the door with that number. If it is your friend's number then you win; if this is a fake number then you have a chance of 1/2 to win. Hence, your total chance of winning with this strategy is 3/4. Is this correct? Is there a better strategy?
Solution
Suppose that $k \ll n$. In that case, your friend can send you the index of the first door containing a treasure. Of the $k$ numbers you get, you pick the smallest one. If $k$ is small enough compared to $n$, then it is very likely that the smallest of the $k$ numbers is the one that your friend sent you.
More concretely, suppose that $k$ is constant. With probability $1-1/n$, the number that your friend sends you is at most $\log n$. The probability that the other $k-1$ numbers are more than $\log n$ is $(1-\log n/n)^{k-1} \approx 1-k\log n/n$. We conclude that this strategy fails with probability at most roughly $1/n + k\log n/n$, which tends to $0$ as $n \to \infty$.
To determine how small $k$ should be, let us be a bit more careful. Denote by $m$ the number that your friend sends you; the distribution of $m$ is geometric (we ignore for now the event in which there are no treasures at all), and so $\Pr[m] = 2^{-m}$. The probability that one of the other $k-1$ numbers is smaller than $m$ is $1-(1-(m-1)/n)^{k-1}$. Overall, this strategy fails with probability
$$
\frac{1}{2^n} + \sum_{m=1}^n 2^{-m} \left(1 - \left(1 - \frac{m-1}{n}\right)^{k-1}\right) = 1 - \sum_{m=1}^n 2^{-m} \left(1 - \frac{m-1}{n}\right)^{k-1}.
$$
We can non-rigorously estimate this as
$$
1 - \sum_{m=1}^\infty 2^{-m}e^{-(m-1)k/n} = 1 - \frac{1}{2-e^{-k/n}} = \frac{1-e^{-k/n}}{2-e^{-k/n}} \approx \frac{k}{n}.
$$
This suggests that if $k = o(n)$ then you win with probability $1-o(1)$.
More concretely, suppose that $k$ is constant. With probability $1-1/n$, the number that your friend sends you is at most $\log n$. The probability that the other $k-1$ numbers are more than $\log n$ is $(1-\log n/n)^{k-1} \approx 1-k\log n/n$. We conclude that this strategy fails with probability at most roughly $1/n + k\log n/n$, which tends to $0$ as $n \to \infty$.
To determine how small $k$ should be, let us be a bit more careful. Denote by $m$ the number that your friend sends you; the distribution of $m$ is geometric (we ignore for now the event in which there are no treasures at all), and so $\Pr[m] = 2^{-m}$. The probability that one of the other $k-1$ numbers is smaller than $m$ is $1-(1-(m-1)/n)^{k-1}$. Overall, this strategy fails with probability
$$
\frac{1}{2^n} + \sum_{m=1}^n 2^{-m} \left(1 - \left(1 - \frac{m-1}{n}\right)^{k-1}\right) = 1 - \sum_{m=1}^n 2^{-m} \left(1 - \frac{m-1}{n}\right)^{k-1}.
$$
We can non-rigorously estimate this as
$$
1 - \sum_{m=1}^\infty 2^{-m}e^{-(m-1)k/n} = 1 - \frac{1}{2-e^{-k/n}} = \frac{1-e^{-k/n}}{2-e^{-k/n}} \approx \frac{k}{n}.
$$
This suggests that if $k = o(n)$ then you win with probability $1-o(1)$.
Context
StackExchange Computer Science Q#48154, answer score: 7
Revisions (0)
No revisions yet.