Sheldon Ross 10: Exercise 3.26

Sheldon Ross 10 Exercise 3.26_poker faces_2.jpg

Question: You have two opponents with whom you alternate play. Whenever you play A, win with probability pA; whenever you play B, you win with probability pB, where pB > pA. If your objective is to minimize the expected number of games you need to play to win two in a row, should you start with A or with B


Analytical Solution: Note that you alternate playing with both the players regardless of whether you lose or win. And you keep doing that until you win two consecutive games.

Let N be the number of the total number of the games that you have played of which two are to be won in order to win the series. The question asks for the best strategy in this case as to which player to play against first so that the expected number of games that you play is minimized.There are two aspects to this problem.

  1. Find the relation between the probabilities and the E[X]
  2. Then minimize the the E[X] by taking the probabilities into account

The first step might seem like its a little bit tricky but we can easily decode that

  1. Let us say that we start with game with A. Then the expected number of games is E[XA]
  2. Then is E[XA] = E[E[XA] | Condition ]
  3. We can condition the expectation on the events that happen during the course of the games as in, the outcomes of the games

E[XA] = E[ E[XA] | outcomes ]] = E[ XA | Win ] P{Win} + E[ XA | Loss ] P{Loss} = E[ XA | Win ] pA + E[ XA | Loss ] (1 – pA)

We realize at this stage that this is recursive branching equation ( more like a hydra 😉 ). The the conditional expectation terms in the expansion further expand into more terms. We will look at them separately.

  • E[ XA | Win ] pA  = E[ XA | Win, Win ] ppB + E[ XA | Win, Loss ] p(1 – pB) = 2 ppB + (2 + E[ X]) p(1 – pB)
  • E[ XA | Loss ] (1 – pA) = (1 + E[ X]) (1 – pA)

Substituting these terms back into the equation above, we get

E[XA] = 1 + pA  + pA(1 – pB) E[ XA ] + (1 – pA) E[ XB ]

and by extension

E[XB] = 1 + pB  + pB(1 – pA) E[ XB ] + (1 – pB) E[ XA ]

The difference of above is

E[XA] – E[XB] = 1 + pA  + pA(1 – pB) E[ XA ] + (1 – pA) E[ XB ] – (1 + pB  + pB(1 – pA) E[ XB ] + (1 – pB) E[ XA ])

ΔX = Δp1+(1-pA)(1-pB)

Where

  • ΔX is the difference in the expected number of steps between A and B
  • Δp is the difference in the probabilities of A and B

The form is now at a stage where we can treat it as an optimization problem. The input are pA and pB and the objective is the ΔX


Simulation Solution

The simulation requires a weighted Random Choice function. All the code required for the simulation is at the bottom of the page.


Code

For this simulation, I have used Python for the data export and Mathematica for the plots.

from sys import stdout
from mathematica.random_functions import RandomReal
from mathematica.lists import Range
import csv

_folderPath = 'your_path_here\\'


def _randomChoiceCustom(_probability):
    _result = 0
    if RandomReal() <= _probability:
        _result = 1
    return _result


_csvfile = open(_folderPath + 'sheldon_ross_10_exercise_3.26.csv', 'w', newline='')
_csvWriter = csv.writer(_csvfile)

_steps = 1000
_subSteps = _steps // 100
_progressPadTop = "-" * 106
_progressPadBottom = "-" * 106
_masterList = []

print("\n\nWriting data to the file :" + _csvfile.name)
print(_progressPadTop)

for i in range(0, _steps):
    _gamesMaster = []
    for _pB in Range(0.1, 0.9, 0.1):
        for _pA in Range(0.1, 0.9, 0.1):
            __i = 0
            _games = []
            _probabilities = [_pA, _pB]
            while True:
                _games.append(_randomChoiceCustom(_probabilities[__i % 2]))
                __i += 1
                if _games[-2:] == [1, 1]:
                    break
            _gamesMaster.append(_games.__len__())
    _csvWriter.writerow(_gamesMaster)

    if (i + 1) % _subSteps == 0:
        stdout.write("\r" + ("\r" + ("#" * (i // _subSteps + 1)).ljust(100)) + " " + str(i // _subSteps + 1) + " %")
        stdout.flush()

print("\n" + _progressPadBottom)
print("Closing the file: " + _csvfile.name)

_csvfile.close()

Needs["JLink`"]
SetOptions[InstallJava, JVMArguments -> "-Xmx8g"];
SetOptions[ReinstallJava, JVMArguments -> "-Xmx8g"];
ReinstallJava[];
AppendTo[$Path, "your_path_here"];
SetOptions[$FrontEndSession,
  EvaluationCompletionAction -> {"ScrollToOutput"}]

Module[
  {data =
      Partition[
        Transpose@
            Import[FileNames["*.csv", NotebookDirectory[]][[1]]],
        9],
    chartLabels = ("\!\(\*SubscriptBox[\(p\), \(A\)]\) = " <> ToString[#]) & /@ Range[0.1, 0.9, 0.1], max = 500},

  Column[
    Framed[#, FrameStyle -> GrayLevel[0.8]] & /@
        Column /@
            Partition[
              MapThread[
                DistributionChart[#1,
                  ImageSize -> 788,
                  ChartElementFunction -> "SmoothDensity",
                  ChartBaseStyle -> Opacity[0.5],
                  GridLines -> {None, Range[100, max, 100]},
                  ChartLabels -> chartLabels,
                  FrameLabel -> {{"", #2}, {"", ""}},
                  AspectRatio -> 0.25,
                  PlotRange -> {All, {0, max}}
                ] &, {data, ("\!\(\*SubscriptBox[\(p\), \(B\)]\) = " <> ToString[#]) & /@ Range[0.1, 0.9, 0.1]}
              ]
              , 3]
  ]
]

End of the Post 🙂


.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.