Use a chance tree to optmize winning

Posted on October 11, 2021

Problem statement (Problem 6.17 from Understanding Probability (Henk Tijms) [Third edition])

In a television game show, you can win 10,000 dollars by guessing the ocomposition of red and white marbles contained in a nontransparent vase. The vase contains a very large number of marbles. You must guess whether the vase has twice as many red marbles as white ones, or whether it has twice as many white ones as red ones. Beforehand, both possibilities are equally likely to you. To help you guess, you are given a one-time opportunity of picking one, two or three marbles out of the vase. This action, however, comes at a cost. If you opt to choose one marble out of the vase, $750 will be subtracted from the $10,000 should you win. Two marbles will cost you $1000 and three marbles will cost you $1500. Set up a chance tree to determine which strategy will help you maximize your winnings.

Approach to the solution

Essentially the problem boils down to this: given an observation what this observation tell us about what urn it came from?

We use chance trees to look at the paths associated with an observation occuring with the highest chance

For example under drawing once, if we observe a red ball what is the probability it came from the red-majority urn?

Let's look at the chance tree (Note: W is a white ball being drawn and R is a red ball being drawn)

Let's try calculating two probabilities to start off:

  1. Probability of the urn being the red dominant one given a red ball has been drawn (1)
  2. Probability of the urn being the white dominant one given a red ball has been drawn (2)

To calculate both, we look at the two paths that end in a red ball being observed (the leaves marked with a R )
and the probability for (1) is \(\frac{0.5 * \frac{2}{3}}{0.5 *(\frac{2}{3} + \frac{1}{3})}\) which is equal to \(\frac{2}{3}\)
and the probability for (2) is \(\frac{0.5 * \frac{1}{3}}{0.5 *(\frac{2}{3} + \frac{1}{3})}\) which is equal to \(\frac{1}{3}\)

So given the observance of a red ball we're more likely to say it came from the red dominant one, so we mark that path in the chance tree as the preferred one to be that "occured" if we see a red ball
Using a similar line of reasoning for a white ball, we mark the route associated with the White ball having a probability of \( 0.5*\frac{2}{3}\) as the preferred one

So, if everytime we observe the colo(u)r of a ball, if we go with the preferred routes, what the are the chances we get it correct?

The formula => \( \frac{\sum P(preferred-route)}{ \sum P(preferred-route) + \sum P(non-preferred-route) } \) which is equal to \( \frac{0.5*(\frac{2}{3} + \frac{2}{3})}{0.5*(\frac{2}{3} + \frac{2}{3}) + 0.5*(\frac{1}{3} + \frac{1}{3})} = \frac{2}{3} \)

It's great we have an answer but it means diddly squat if we can't verify it in some way

We are blessed with the modern computer that can run simulation for most of our probablistic experiments in a reasonable time. We'll be using clojure to write a simulation to verify our theoretical estimate above. The code will be written in alphabet tagged fragments because we'll be reusing them further along

(A) 

;; code to create an infinite stream representing an infinitely large red-dominant urn
(defn red-dominant   [] (repeatedly #(rand-nth [:red :red :white])))
;; code to create an infinite stream representing an infinitely large white-dominant urn
(defn white-dominant [] (repeatedly #(rand-nth [:red :white :white])))

To reiterate our strategy (for draw once) is to draw a ball, if it is red in colour we predict the urn to be the red-dominant one and if it's white, we predict the urn to be the white-dominant one

This in clojure is as follows (won't bother alphabet tagging this as we'll be using this once) 

(defn predict-1 [urn]
  (if (= (first urn) :red)
    :red-dom
    :white-dom))

The rest of the utility to actually use this and execute the trials and tally results are as follows

(B) 


;; produces a white-dominant urn or a red-dominant urn stream
;; half of the time and checks to see if the prediction against the stream is correct
;; outputs a boolean
(defn trial [prediction-func]
  (let [[x f]      (rand-nth [[:red-dom red-dominant]
                              [:white-dom white-dominant]])]
    (= (prediction-func (f)) x)))

;; list that tallies number of trues from a sequence of boolean values
(defn counter [list]
  (let [freq (frequencies list)
        t-count (get freq true 0)
        f-count (get freq false 0)]
    (/ (float t-count) (+ t-count f-count))))

;; main function to run
(defn calculate [prediction-fn]
  (counter (repeatedly 1000000 #(trial prediction-fn))))
Assuming A, B and the predict-1 are loaded in the repl, if we run the following snippet 

(calculate predict-1) ;; we should get around 0.66716

The output is consistent with our theoretical prediction

Warning: That was the easy part. Now moving on to the two draws part

Let's look at the chance tree for two draws

There are two things to note here

  1. RW in the leaf refers to both permutations i.e RW and WR
  2. In contrast to the one draw, we are now left with draw states that have equal probability of being matched with either urn ... making predicition troublesome. Interestingly more troublesome than just the one draw. You'd think more evidence makes for easier predictability

Let's look at the strategy for the two draws in two parts

  1. Part 1 doesn't consider the equal probability draw states as preferred paths (i.e RW, WR) [spoiler alert: this doesn't end well]
  2. Part 2 does consider the equal probability draw states as preferred paths [spoiler alert: it doesn't do much in a relative sense]

Two draws: Part 1: Theoretical Calculation

\( \frac{\sum P(preferred-route)}{ \sum P(preferred-route) + \sum P(non-preferred-route) } \) which is equal to \( \frac{0.5*(\frac{4}{9} + \frac{4}{9})}{0.5*(\frac{4}{9} + \frac{4}{9} + \frac{1}{9}) + 0.5*(\frac{4}{9} + \frac{4}{9} + \frac{1}{9})} = \frac{4}{9} \) = 0.44444

Pretty bad odds huh? We are kicking out quite a lot by letting the equal states go to waste

Two draws: Part 1: Simulation results

(C) 

(defn predict-2a [urn]
  (let [draws (take 2 urn)]
    (cond
      (= draws [:red :red]) :red-dom
      (= draws [:white :white]) :white-dom
      :else nil)))
Assuming A, B and the predict-1 are loaded in the repl, if we run the following snippet 

(calculate predict-2a) ;; we should get around 0.444175

Two draws: Part 2: Theoretical Calculation

Here we decide to predict red-dominant urn when confronted with any permutation of RW

\( \frac{\sum P(preferred-route)}{ \sum P(preferred-route) + \sum P(non-preferred-route) } \)

which is equal to \( \frac{0.5*(\frac{4}{9} + \frac{4}{9} + \frac{4}{9})}{0.5*(\frac{4}{9} + \frac{4}{9} + \frac{1}{9}) + 0.5*(\frac{4}{9} + \frac{4}{9} + \frac{1}{9})} = \frac{6}{9} \) = 0.6666...

Two draws: Part 2: Simulation results

for this simulation ode, we make a slight adjustment to the previously defined code fragment (C) 


(defn predict-2b [urn]
  (let [draws (take 2 urn)]
    (cond
      (= draws [:red :red]) :red-dom
      (= draws [:white :white]) :white-dom
      :else :red-dom ; modified part
  )))
Assuming A, B and the predict-2b are loaded in the repl, if we run the following snippet 

(calculate predict-2b) ;; we should get around 0.666013

The output is consistent with our theoretical prediction

Note:

For part 2, you'd get the same results when you sub in the below for prediction when you hit any permutation of RW

  1. (given) predict red dominant urn
  2. predict white dominant urn (reason: same as above)
  3. switch randomly between red dominant urn and white dominant (reason: see Prove that every head-tail sequence is 50% equal to every other head-tail sequence of the same length (on average) )

Now Let's look at the chance tree for three draws

There are two things to note here

  1. RRW in the leaf refers to all permutations i.e RRW, RWR and WRR
  2. RWW in the leaf refers to all permutations i.e RWW, WRW and WWR
  3. In contrast to the two draw part, we do have qual draw states that have equal probability of being matched with either urn ... making prediction sooooo much nicer
Our strategy is (for straightforward reasons) :
  1. if we draw RRR, we predict red dominant urn
  2. if we draw RRW (any permutation), we predict red dominant urn
  3. if we draw RWW (any permutation), we predict white dominant urn
  4. if we draw WWW (any permutation), we predict white dominant urn

Let's see how this strategy fairs theoretically and in simulation

Three draws: Theoretical Calculation

\( \frac{\sum P(preferred-route)}{ \sum P(preferred-route) + \sum P(non-preferred-route) } \)

which is equal to \( \frac{0.5*(\frac{8}{27} + \frac{12}{27} + \frac{12}{27} + \frac{8}{27})}{0.5*(\frac{8}{27} + \frac{12}{27} + \frac{12}{27} + \frac{8}{27}) + 0.5*(\frac{1}{27} + \frac{1}{27} + \frac{6}{27} + \frac{6}{27})} = \frac{20}{27} \) = 0.74074074

Three draws: Simulation

for this simulation ode, we make a slight adjustment to the previously defined code fragment (C) 


(defn predict-3 [urn]
  (let [red-draws (-> (take 3 urn)
                      frequencies
                      (get :red))]
    (condp = red-draws
      3 :red-dom
      2 :red-dom
      1 :white-dom
      0 :white-dom)))
Assuming A, B and the predict-3 are loaded in the repl, if we run the following snippet 

(calculate predict-3) ;; we should get around 0.74074

The output is consistent with our theoretical prediction

Results

Draw 3 at 1500 it is!!!!