Conjecture on the optimal strategy for dependent Bernoulli variables

From papers

Let I1,I2,...,InI_{1},I_{2},...,I_{n} be nn dependent Bernoulli random variables, and let

pi,k:=P(Ii=1Ik=1).p_{i,k}:=P(I_{i}=1\mid I_{k}=1).

Optimal-strategy conjecture. After observing Ik=1I_{k}=1, the player whose turn it is should give up his turn to his opponent if and only if pi,k<12p_{i,k}<\frac{1}{2} for all i>ki>k. This predicts that the adversarial Last-Success-Problem remains simple for dependent variables, with the decision determined by the conditional success probabilities of the remaining variables. The conjecture is presented as a prediction in the source; no resolution is given.

Progress summary

Open

No publicly sourced proof or counterexample has been found, so the conjecture remains open.

The conjecture says that after observing Ik=1I_k=1, a player should pass exactly when every later conditional success probability satisfies pi,k<12p_{i,k}<\frac{1}{2}. It appears as Conjecture 1 in a paper on the adversarial Last-Success-Problem, which gives no proof or resolution.

Current status (as of August 2026): The conjecture remains unsettled; the retrieved public record contains its formulation but no verified proof, counterexample, or claimed resolution.

Sources
Sources & referencesView supporting material

Primary source

José María Grau Ribas, “Concerning an adversarial version of the Last-Success-Problem”, arXiv:1812.05381 (2019).

Solutions 1

Counterexample

The proposed rule fails in both directions, even for three Bernoulli variables with full joint support. Moreover, identical future conditional success probabilities can require opposite optimal decisions.

Take n=3n=3, let I1I_1 be an independent fair Bernoulli variable, and condition on I1=1I_1=1. Write

pab=P(I2=a,I3=bI1=1),a,b{0,1}.p_{ab}=\mathbb P(I_2=a,I_3=b\mid I_1=1), \qquad a,b\in\{0,1\}.

If the current player retains the turn, optimal backward induction gives the winning probability

V=p01+max{p10,p11}.(1)V=p_{01}+\max\{p_{10},p_{11}\}. \tag{1}

Indeed, on I2=0I_2=0, the player cannot pass and wins exactly when I3=1I_3=1, contributing p01p_{01}. On I2=1I_2=1, retaining wins on outcome 1111, whereas passing wins on outcome 1010, contributing the larger of p11p_{11} and p10p_{10}. Passing immediately after I1=1I_1=1 instead wins with probability 1V1-V.

First, take

(p00,p01,p10,p11)=110(3,3,3,1).(p_{00},p_{01},p_{10},p_{11}) = \frac1{10}(3,3,3,1).

Then

P(I2=1I1=1)=P(I3=1I1=1)=25<12.\mathbb P(I_2=1\mid I_1=1) = \mathbb P(I_3=1\mid I_1=1) = \frac25<\frac12.

The conjecture therefore prescribes passing. But

V=310+max{310,110}=35,V=\frac3{10}+\max\left\{\frac3{10},\frac1{10}\right\} =\frac35,

so retaining wins with probability 3/53/5, while passing wins with probability 2/52/5.

Conversely, take

(p00,p01,p10,p11)=120(7,1,7,5).(p_{00},p_{01},p_{10},p_{11}) = \frac1{20}(7,1,7,5).

Here

P(I2=1I1=1)=35>12,\mathbb P(I_2=1\mid I_1=1)=\frac35>\frac12,

so the conjecture prescribes retaining. Nevertheless,

V=120+max{720,520}=25,V=\frac1{20}+ \max\left\{\frac7{20},\frac5{20}\right\} = \frac25,

and passing is strictly optimal, with winning probability 3/53/5.

Finally, taking

(p00,p01,p10,p11)=15(2,1,1,1)(p_{00},p_{01},p_{10},p_{11}) = \frac15(2,1,1,1)

gives the same two conditional success probabilities (2/5,2/5)(2/5,2/5) as the first example, but now

V=25,V=\frac25,

so the optimal decision is the opposite. Thus even the complete list of future one-coordinate conditional success probabilities does not determine the optimal action. All eight joint outcomes of (I1,I2,I3)(I_1,I_2,I_3) have strictly positive probability in every example.

0 endorsements
Shivam Patel ·