5

A small boy is lost coming down Mount Washington. The leader of the search team estimates that there is a probability $p$ that he came down on the east side and a probability $1 − p$ that he came down on the west side. He has $n$ people in his search team who will search independently and, if the boy is on the side being searched, each member will find the boy with probability $u$. Determine how he should divide the $n$ people into two groups to search the two sides of the mountain so that he will have the highest probability of finding the boy. How does this depend on $u$?

No idea where to start. The answer has couple $\log$s in it. That's from a chapter of the book where I've learned this: https://i.stack.imgur.com/sbGj0.png. Perhaps I'm supposed to use some kind of derivative over $p$ somewhere along the way? But then I can't really come up with what to differentiate.

The Phenotype
  • 5,199
Max
  • 1,275
  • For now the problem is rather discrete so let's focus on what we have. What happens if you send $1 $ person on the $ p $ side and the rest of the team on the other side, assuming the rest of the team is made of $2 $ people? – Arnaud Mortier Jan 27 '18 at 11:01
  • @ArnaudMortier perhaps the one person will find the boy with probability $pu$? :\ And for the two persons, I suppose we need to calculate the probability that either one or all of them will find the boy and then multiply it be $(1-p)$? – Max Jan 27 '18 at 11:44
  • There won't be any reason to take derivatives. Let $f(k)$ be the probability of success if the leader sends $k$ people to the east side. We just need to know when $f(k+1)>f(k).$ – saulspatz Jan 27 '18 at 11:44
  • @Max for $pu$ you are correct. For the other side it is easier to compute the probability that none of them finds the boy and then take $1-$that. And indeed multiply the result by $1-p$. – Arnaud Mortier Jan 27 '18 at 11:53
  • @saulspatz it's a bit trickier than that, there are the $n-k$ people on the other side, who could find the boy as well. – Arnaud Mortier Jan 27 '18 at 12:07
  • @ArnaudMortier I mean of course, that he also sends $n-k$ people to the west side, as stated in the problem. – saulspatz Jan 27 '18 at 18:37

2 Answers2

3

This is a partial answer only.

If you send $k$ people to the $p$ side, the probability that the boy is not found is $$p(1-u)^k+(1-p)(1-u)^{n-k}$$ Hence the probability that the boy is found is $$f(k)=1-p(1-u)^k-(1-p)(1-u)^{n-k}$$

Therefore you need to find the maximum of the function $$f(x)=1-p(1-u)^x-(1-p)(1-u)^{n-x}$$

whose derivative is $$f^\prime(x)=-p\ln(1-u)(1-u)^x+(1-p)\ln(1-u)(1-u)^{n-x}$$

Now this vanishes when $$(1-p)(1-u)^{n-x}=p(1-u)^x$$ That is $$\frac{1-p}{p}(1-u)^{n}=(1-u)^{2x}$$ Taking logs $$\ln(\frac{1-p}{p})+n\ln(1-u)=2x\ln(1-u)$$ Finally $$x=\frac{1}{2}\left(n+\dfrac{\ln(1-p)-\ln(p)}{\ln(1-u)}\right)$$

Now this is probably not an integer, so you still need to find which of the two nearest integers is the best.

Arnaud Mortier
  • 27,276
1

Let $f(k)$ be the probability of failure if the leader sends $k$ people to the east side and $n-k$ people to the west side. As explained in Arnaud Mortier's solution, $$f(k) = pv^k + (1-p)v^{n-k},$$ where $v = 1-u.$ Since $k$ is a discrete variable, we can minimize $f$ by comparing its values at successive values of $k.$

$$f(k) \le f(k-1) \Leftrightarrow pv^{k}+(1-p)v^{n-k}\le pv^{k-1}+(1-p)v^{n-k+1} $$ $$\Leftrightarrow pv^k-pv^{k-1} \le (1-p)v^{n-k+1}-(1-p)v^{v-k}$$ $$\Leftrightarrow pv^{k-1}(v-1) \le (1-p)v^{n-k}(v-1)$$ $$\Leftrightarrow \frac{p}{1-p} \ge v^{n-2k-1} \Leftrightarrow \frac{\log p -\log (1-p)}{\log v} \ge n- 2k -1$$ $$\Leftrightarrow k \ge \frac{n-1}{2} - \frac{\log p - \log (1-p)}{2\log(1-u)} $$ Since we want the largest value of $k$ for which this holds, we take $$k = \Big \lfloor \frac{n-1}{2} - \frac{\log p - \log (1-p)}{2\log(1-u)} \Big \rfloor$$

I would appreciate it if someone would improve the formatting of this answer. My MathJax skills are still rather rudimentary.

saulspatz
  • 53,131