Let $U_1,U_2,\ldots,U_n$ be $n\geq 2$ mutually independent Bernoulli random variables. There are two cases of interest:

$1.$ The random variables $U_1,U_2,\ldots,U_n$ are identically distributed;

• $U_1\sim \operatorname{Bernoulli}(p)$ with probability $1/2$. Let $P_0$ be the associated probability measure, i.e. $$P_0(U_1,\ldots,U_n)=P(U_1,\ldots,U_n\mid U_1\sim \operatorname{Bernoulli}(p))$$

• $U_1\sim \operatorname{Bernoulli}(1-q)$ with probability $1/2$. Let $P_1$ be the associated probability measure, i.e. $$P_1(U_1,\ldots,U_n)=P(U_1,\ldots,U_n\mid U_1\sim \operatorname{Bernoulli}(1-q))$$

There are two sets defined:

$$\mathcal{S}_0=\left\{\{u_1,\ldots,u_n\}:\prod_{k=1}^n P_1(U_k=u_k)\leq \prod_{k=1}^n P_0(U_k=u_k)\right\}$$

$$\mathcal{S}_1=\left\{\{u_1,\ldots,u_n\}:\prod_{k=1}^n P_1(U_k=u_k)> \prod_{k=1}^n P_0(U_k=u_k)\right\}$$

and the corresponding objective function:

$$R(n,(p,q))=\frac{1}{2}\left(\sum_{\{u_1,\ldots,u_n\}\in \mathcal{S}_0} \prod_{k=1}^n P_1(U_k=u_k)+\sum_{\{u_1,\ldots,u_n\}\in \mathcal{S}_1} \prod_{k=1}^n P_0(U_k=u_k)\right)$$

$2.$ The random variables $U_1,U_2,\ldots,U_n$ are not necessarily identically distributed;

• $U_k\sim \operatorname{Bernoulli}(p_k)$ with probability $1/2$. Let $P_0^k$ be the associated probability measure, i.e. $$P_0^k(U_k)=P(U_k\mid U_k\sim \operatorname{Bernoulli}(p_k))$$

• $U_k\sim \operatorname{Bernoulli}(1-q_k)$ with probability $1/2$. Let $P_1^k$ be the associated probability measure, i.e. $$P_1^k(U_k)=P(U_k\mid U_k\sim \operatorname{Bernoulli}(1-q_k))$$

There are two sets defined:

$$\mathcal{S}_0^*=\left\{\{u_1,\ldots,u_n\}:\prod_{k=1}^n P_1^k(U_k=u_k)\leq \prod_{k=1}^n P_0^k(U_k=u_k)\right\}$$

$$\mathcal{S}_1^*=\left\{\{u_1,\ldots,u_n\}:\prod_{k=1}^n P_1^k(U_k=u_k)> \prod_{k=1}^n P_0^k(U_k=u_k)\right\}$$

and the corresponding objective function with $(\mathbf{p},\mathbf{q})=((p_1,q_1),(p_2,q_2),\ldots,(p_n,q_n))$ is:

$$R^*(n,(\mathbf{p},\mathbf{q}))=\frac{1}{2}\left(\sum_{\{u_1,\ldots,u_n\}\in \mathcal{S}_0^*}\prod_{k=1}^n P_1^k(U_k=u_k)+\sum_{\{u_1,\ldots,u_n\}\in \mathcal{S}_1^*}\prod_{k=1}^n P_0^k(U_k=u_k)\right)$$

The success probability of the random variable $U_1$ for case $1$, i.e. $(p,1-q)$ and the success probabilities of the random variables $U_1,\ldots,U_n$, i.e. $(p_1,1-q_1),\ldots,(p_n,1-q_n)$ for case $2$ are defined on a continuous convex curve $C_\theta$, which passes through all the points $(p,q)$ as well as $(0,1), (\theta,\theta), (1,0)$. An example of $C_\theta$ is given below with a blue curve and $\theta=0.3$. The set of all such curves are denoted by $\mathcal{C}_\theta$ and any element of $\mathcal{C}_\theta$, i.e. any continuous convex curve $C_{\theta=0.3}$ must be in the orange area given in the figure, due to convexity.

Notice that $C_\theta$ is a convex curve of the points $(p,q)$, whereas the success probabilities are $p$ and $1-q$, each with $1/2$ probability as defined above.

The question that I have is to find the function $W$ which is defined as:

$$W(n)=\max_{\theta\in(0,0.5)}\max_{C_\theta\in\mathcal{C}_\theta}\left[ \min_{(p,q)\in C_\theta} R(n,(p,q))-\min_{\forall k, (p_k,q_k)\in C_\theta} R^*(n,(\mathbf{p},\mathbf{q}))\right]$$

Here $\max_{\theta\in(0,0.5)}\max_{C_\theta\in\mathcal{C}_\theta}$ corresponds to all such convex curves. One can just put a single $\max$.

My Own Work:

For case $1$, I am able to simplify the problem considerably as follows:

Assume we are given a certain $\{u_1,\ldots,u_n\}$. It will have $r$ times $1$s and $n-r$ times $0$s.

The condition to assign it to either $\mathcal{S}_0$ or $\mathcal{S}_1$ is $$\prod_{k=1}^n \frac{P_1(U_k=u_k)}{P_0(U_k=u_k)}\lessgtr 1\Longrightarrow \sum_{k=1}^n \log\frac{P_1(U_k=u_k)}{P_0(U_k=u_k)}\lessgtr 0$$ Since $U_k$ are identically distributed above given condition can be written as $$r\log\frac{P_1(U_k=1)}{P_0(U_k=1)}+(n-r)\log\frac{P_1(U_k=0)}{P_0(U_k=0)}\lessgtr 0$$ which can be rewritten as $$n\log\frac{P_1(U_k=0)}{P_0(U_k=0)}+r\left(\log\frac{P_1(U_k=1)}{P_0(U_k=1)}-\log\frac{P_1(U_k=0)}{P_0(U_k=0)}\right)\lessgtr 0$$ Hence, we have $$r\lessgtr \frac{n\log\frac{P_1(U_k=0)}{P_0(U_k=0)}}{\log\frac{P_1(U_k=0)}{P_0(U_k=0)}-\log\frac{P_1(U_k=1)}{P_0(U_k=1)}}\Longrightarrow r\lessgtr t=\frac{n\log\frac{q}{1-p}}{\log\frac{pq}{(1-p)(1-q)}}$$ Here we have $r=\sum_{k=1}^n U_k\sim \operatorname{Binomial}(n)$. Hence, $$\mathcal{S}_0=\{\{u_1,\ldots,u_n\}:r\leq t\}\\ \mathcal{S}_1=\{\{u_1,\ldots,u_n\}:r> t\}$$ and as a result of above $$\sum_{\{u_1,\ldots,u_n\}\in \mathcal{S}_0}\prod_{k=1}^n P_1(U_k=u_k)=P[r\leq t\mid U_1\sim\operatorname{Bernoulli}(1-q)]=\sum_{k=0}^t\binom{n}{k}(1-q)^k q^{n-k}\\ \sum_{\{u_1,\ldots,u_n\}\in \mathcal{S}_1}\prod_{k=1}^n P_0(U_k=u_k)=P[r>t\mid U_1\sim\operatorname{Bernoulli}(p)]=1-\sum_{k=0}^t\binom{n}{k}p^k (1-p)^{n-k}$$ Consequently, $$R(n,(p,q))=\frac{1}{2}+\frac{1}{2} \sum_{k=0}^t\binom{n}{k} \left[(1-q)^k q^{n-k}+p^k(1-p)^{n-k}\right]$$ where $$t=\frac{n\log\frac{q}{1-p}}{\log\frac{pq}{(1-p)(1-q)}}$$ as found above.

For case $2$, the things are getting complicated because each $U_k$ is Bernoulli with different success probabilities. What I have is the following:

$$\{u_1,\ldots,u_k=0,\ldots,u_n\}\in\mathcal{S}_1^*\Longrightarrow \{u_1,\ldots,u_k=1,\ldots,u_n\}\in\mathcal{S}_1^*$$ Similarly, $$\{u_1,\ldots,u_k=1,\ldots,u_n\}\in\mathcal{S}_0^*\Longrightarrow \{u_1,\ldots,u_k=0,\ldots,u_n\}\in\mathcal{S}_0^*$$

This is because of the convexity of $C_\theta$, i.e. $$\frac{P_1(U_k=1)}{P_0(U_k=1)}=\frac{1-q}{p}\geq \frac{P_1(U_k=0)}{P_0(U_k=0)}=\frac{q}{1-p}$$

as $$(1-p)(1-q)\geq pq\Longrightarrow 1-p-q\geq 0$$ is true due to convexity of $C_\theta$. This says that one can populate the sets $\mathcal{S}_0^*$ and $\mathcal{S}_1^*$ with (much) less than $2^n$ computations.

I can also write $R^*(n,(\mathbf{p},\mathbf{q}))$ in terms of $p_k$s and $q_k$s as follows:

$$R^*(n,(\mathbf{p},\mathbf{q}))=\frac{1}{2}\left(\sum_{\{u_1,\ldots,u_n\}\in \mathcal{S}_0^*}\prod_{u_k=0}q_k \prod_{u_k=1}(1-q_k)+\sum_{\{u_1,\ldots,u_n\}\in \mathcal{S}_1^*}\prod_{u_k=0}(1-p_k)\prod_{u_k=1}p_k \right)$$

Accordingly,

$$R(n,(p,q))-R^*(n,(\mathbf{p},\mathbf{q}))=\left(\frac{1}{2}+\frac{1}{2} \sum_{k=0}^t\binom{n}{k} \left[(1-q)^k q^{n-k}+p^k(1-p)^{n-k}\right]\right)-\left(\frac{1}{2}\left(\sum_{\{u_1,\ldots,u_n\}\in \mathcal{S}_0^*}\prod_{u_k=0}q_k \prod_{u_k=1}(1-q_k)+\sum_{\{u_1,\ldots,u_n\}\in \mathcal{S}_1^*}\prod_{u_k=0}(1-p_k)\prod_{u_k=1}p_k \right)\right)$$

This function needs to be maximized over all convex continuous curves for the minimizing $(p,q)$ and $(\mathbf{p},\mathbf{q})$.

I think the critical point is to come up with a suitable convex curve. I cannot even guess what kind of convex curve would likely maximize the above. I am desperate even for the simplest case: $n=2$.

I have the feeling that this question is rather difficult but I still would like to attack. I would be grateful in this regard for any help.