Sixteen players must cross a bridge, in single file, by stepping on panes of glass. There are eighteen pairs of panes: one will hold a person’s weight, the other will not. Eighteen times the player in front must make a choice: do they step on the left pane, or the right? A 50-50 gamble between being one step closer to salvation and plummeting to their demise.

Once a choice is made for a pair, the front player will live or die but all other players will be guaranteed to make a successfull choice for that particular pair. Either they have seen which pane is correct, or the faulty pane breaks and only the correct one remains.

If the person in front dies, the person behind them becomes the new person in front and the game continues. The game ends when all players are dead or the front player reaches the final pane.

Meanwhile, in a lavish room overlooking the bridge, a handfull of masked sadists place bets on who live and who will die…

Surely, players in the back have better odds. But how much better? Although human factors do weigh in, there is a basis of probability theory that will give a better insight in each player’s odds of survival.

Looking at this problem from a purely mathematical point of view, what is each player’s probability of reaching the eighteenth pane alive and well? This is not entirely straightforward because the odds of a player’s success depend on the successes of the players in front.

In case you’re only interested in the actual probabilities, I put them before the bulk of this article.

The goal of this article is to provide an informal reference to my programming students and anyone interested in calculating probabilities leaning more on programming than on mathematics. I discuss a general approach using the brigde problem as a concrete example.

Yes, this particular example can be calculated more efficiently and elegantly. I use this particular example from popular media to to discuss a general approach which can be applied more broadly.

This approach can be implemented in many different ways. You can find my implementation, including the code that generated the results, .

Now let’s get started!

Results

The probabilities of reaching a pane alive and well:

What a lovely spiral pattern.

The probabilities of surviving by reaching the eighteenth pane:

Probability theory refresher

An event is something we want to calculate the probability of. E.g. ‘player 1 successfully reached pane 8’.

If a situation has multiple possible outcomes, each with a probability, the sum of all these probabilities is 1 (which is equal to 100%).

The probability of an event is the sum of the probabilities of the outcomes in which the event occurs/holds true.

To calculate the probability of an event, we must know all possible outcomes and their respective probabilities.

You might not have seen the distinction between event and outcome before. As an example let’s consider the situation of throwing two regular dice. If we are interested in events such as ‘the total value thrown is 7’, then you could say the outcomes are the numbers 2 up to and including 12. Each outcome directly represents an event.

But what if we’re also interested in the event ‘both dice have the same value’? Then these 11 outcomes don’t contain enough information. To be able to measure both types of events in the outcomes, there should be 6 * 6 = 36 outcomes, one for each pair of values.

Only if exactly one event will occur in any given outcome, then it is safe to represent outcomes and events as the same thing. When outcomes can satisfy zero or multiple events, we have to explicitly separate the two concepts.

For a single outcome we can determine for multiple events if they occur in the outcome or not.

Approach

To calculate the probability of an event, we must know all possible outcomes and their respective probabilities. Sometimes these are trivial to determine and straightforward mathematics will easily get the job done. However, when either the possible outcomes or their respective probabilities aren’t obvious, this programmatic approach comes in handy.

This is what the approach looks like in general:

• Create a state transition graph
  • One initial state
  • A state has either
    • One or more transitions
      • Each transition
        • Has a probability
        • Leads to another state
    • Zero transitions: is an end state
  • Keep adding states until all end states are reached
• The end states represent the possible outcomes
• The probability of reaching an end state is the sum of the probabilities of all paths from the initial state to this end state
• Calculate the probabilities of the events using the end states (outcomes) and their respective probabilities

For our glass bridge problem we are interested in the probabilities of these events:

1
2
3
4
5
6
7

player  1 successfully reached pane  1
player  1 successfully reached pane  2
...
player  1 successfully reached pane 18
player  2 successfully reached pane  1
...
player 16 successfully reached pane 18

16 * 18 = 288 events. Yikes.

Manual calculation

Let’s start with a smaller version of this problem so it’s easier to get the approach right on paper first. Writing code is cool and all, but expressing your ideas is usually much faster and easier done by sketching on paper. Iterate quickly, get the mistakes out early!

Let’s say we have 1 player and 3 panes. Now these are our events:

1
2
3

player 1 succesfully reached pane 1
player 1 succesfully reached pane 2
player 1 succesfully reached pane 3

To calculate their probabilities, we

1. construct the state transition graph
2. for each end state determine its probability
3. for each [end state, event] pair, check if the event occurs in that end state

The initial state is player 1 not having stepped on any pane yet. Each state has two outcomes: player 1 stepped on either the correct pane and lives, or the faulty pane and died.

We’re assuming each transition has a probability of 1/2. The probability of an end state is the sum of the probabilities of each path from the root to this end state. For this bridge problem, luckily all end states are reached by only a single path. So each end state’s probability is the product of the transitions that make up the one path that leads to it:

There are two sanity checks we can do to see if we aren’t making any mistakes.

For each state, if it has any outgoing transitions, their probabilities should sum to 1. In our case, if a state has outgoing transitions there are two of them, both with a probability of 1/2. All good.

The probabilities of all end states should sum to 1. 1/8 + 1/8 + 1/4 + 1/2 = 1. All good again!

Now we cross-check our events and end states. For reference, let’s call the end states 1, 2 3 and 4, from top to bottom.

Finally, we can calculate the probability of each event.

1
2
3
4

  p(player 1 succesfully reached pane 1)
= p(end state 1) + p(end state 2) + p(end state 3)
= 1/8 + 1/8 + 1/4
= 1/2

Doing so for all events results in

Nice!

I can feel the skepticism radiating from your visage. For this small example, the probabilities were trivial indeed. We could have easily come to these results with straightforward mathematics. But lo! a is less obvious example is abound!

Writing a program

For the situation 3 players, 3 panes, spend a minute or so trying to calculate the probability of event ‘player 3 successfully reached pane 3’ with conventional mathematics. Not so trivial anymore.

Not to mention the sheer labor required to calculate the results for 16 players and 18 panes. 288 events! 262,125 end states! 75,492,000 cross-checks!

Time to write a program. This will be its general structure:

(All code in this article is pseudocode, definitely not JavaScript. The code blocks say ‘JavaScript’ for syntax highlighting.)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

function is_end_state(state) {
  ...  
}

initial_state     = ...

states_to_process = stack(initial_state)
end_states        = []

while (states_to_process not empty) {
  state = states_to_process.top
  
  states_to_process.remove_top()

  if (is_end_state(state)) {
    end_states.add(state)
  } else {
    // for each new state
    new_state = ...
    states_to_process.add(new_state)
  }
}

Starting with the initial state, by iteratively taking a state from a stack and putting its children back on the stack, we create all states in a depth-first order.

The main component is a state. How to model a state? Modeling is an iterative process. You start somewhere and add or change things as you introduce more ways in which you want to use your model.

Ultimately a state needs to contain enough information to:

• Decide if it’s an end state
• If not an end state, create its next states

And specifically for our bridge problem:

• Decide if a given player ever successfully reached a given pane

To decide if a state is an end state, the model should encode:

• If any players are left alive
• The furtherst reached pane

Using the initial state as an example, a first model could look something like:

1
2

{any_player_alive = true
 pane             = 0}

To model the next states, we should be able to know when we go from any player alive to no players alive. Having only a boolean any_player_alive, there’s no way of telling. We need to make a change:

1
2

{num_players_alive = 3
 pane              = 0}

Now we can decrease num_players_alive when the player in front dies and we know exactly when to go to no players left.

Finally, we need to be able to deduce all panes a player has successfully reached. The current model doesn’t contain enough information. If there is a single player (player 3) alive on pane 3, player 2 could have come as far as pane 3, or perhaps only as far as pane 2. Let’s add a field:

1
2
3
4
5
6

{num_players_alive = 3
 pane              = 0
 last_alive        = [{player = 1
                       pane   = 0},
                      {player = 2
                       pane   = 3}]}

This model encodes everything we need to know!

We can determine which player died (so an element can be added to last_alive) based on num_players_alive. However, if we make a small change to the model we can determine this in a slightly more simple way. In the changed model, the initial state looks like this:

1
2
3

{alive      = [1, 2, 3]
 pane       = 0
 last_alive = []}

Now the players that are still alive are modeled directly instead of indirectly. We need fewer deductions to obtain the information we actually want to encode. The model has become more simple from a conceptual point of view, at the cost of more data and perhaps more expensive operations as working with collections tends to be slower than working with numbers. I prefer to go for a simpler model until I can no longer afford to.

Knowing how to model states, we can flesh out our program:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

function is_end_state(state) {
  return (state.alive is empty) or (state.pane == 3) 
}

initial_state = {alive      = [1, 2, 3]
                 pane       = 0
                 last_alive = []}

states_to_process = stack(initial_state)
end_states = []

while (states_to_process not empty) {
  state = states_to_process.top
  
  states_to_process.remove_top()

  if (is_end_state(state)) {
    end_states.add(state)
  } else {
    
    new_state_success =
      {alive      = state.alive
       pane       = state.pane + 1
       last_alive = state.last_alive}
    
    states_to_process.add(new_state_success)
      
    
    dead_player = state.alive.first
    new_state_failure =
      {alive      = state.alive.without_first()
       pane       = state.pane + 1
       last_alive = state.last_alive.add({player = dead_player
                                          pane   = state.pane})}

    states_to_process.add(new_state_failure)
  }
}

Which results in an end_states that looks something like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

[
  {alive      = []
   pane       = 3
   last_alive = [{player = 1, pane = 1}
                 {player = 2, pane = 3}
                 {player = 3, pane = 3}]},
 ...
  {alive      = [1, 2, 3]
   pane       = 3
   last_alive = []}
]

We have our end states (outcomes), but what about probabilities? We didn’t store any transitions!

Instead of storing transitions and traversing paths, we could store the probability of the path that reaches a state in the state itself. For the initial state, this probability defaults to 1.

When we create a state’s child, we multiply the state’s probability by the probability of the transition to that child. This extends the path to the parent state by that transition, effectively creating the path to the child. The probability of the extended path is stored in the child.

Beware! If states are reachable via multiple paths we have to be more careful. Each time a path comes to a state, there might already be a probability for that state. The probability of the extended path should be added to any existing probability, not override it.

Also in case of multiple paths reaching a state, before a state can be processed all of its parents must be processed. If not all parents have been processed yet, the state’s probability is incomplete and can’t be used to calculate the probability of its children. Processing the states in a breadth-first order will ensure all parents are processed first. I won’t go into more detail, but if you spend some time sketching an example on paper you’ll see.

However, for our bridge problem all states are reached by a single path only. We can get away with immediately calculating each state’s final probability in a depth-first order.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

function is_end_state(state) {
  return (state.alive is empty) or (state.pane == 3) 
}

initial_state = {p          = 1
                 alive      = [1, 2, 3]
                 pane       = 0
                 last_alive = []}

states_to_process = stack(initial_state)
end_states = []

p_success = 1/2

while (states_to_process not empty) {
  state = states_to_process.top
  
  states_to_process.remove_top()

  if (is_end_state(state)) {
    end_states.add(state)
  } else {
    
    new_state_success =
      {p          = state.p * p_success
       alive      = state.alive
       pane       = state.pane + 1
       last_alive = state.last_alive}
    
    states_to_process.add(new_state_success)
      
    
    dead_player = state.alive.first
    new_state_failure =
      {p          = state.p * (1 - p_success)
       alive      = state.alive.without_first()
       pane       = state.pane + 1
       last_alive = state.last_alive.add({player = dead_player
                                          pane   = state.pane})}

    states_to_process.add(new_state_failure)
  }
}

Which results in this end_states:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

[
  {p          = 1/8
   alive      = []
   pane       = 3
   last_alive = [{player = 1, pane = 1}
                 {player = 2, pane = 3}
                 {player = 3, pane = 3}]},
  ...
  {p          = 1/8
   alive      = [1, 2, 3]
   pane       = 3
   last_alive = []}
]

Now that we know the probabilities of the end states we can calculate the probabilities of our events. What is the probability of player 2 being having successfully reached pane 2? Sum the probabilities of the end states in which player 2 has successfully reached pane 2…

There are many ways to do this, which I won’t discuss further. If you want to check your implementation, here are the probabilities of each player successfully reaching each pane:

Closing words

You’ve seen an approach for calculating probabilities based on state transitions. It comes in handy when either is not trivial to find:

• all outcomes of a situation
• the probability of each outcome

A summary of the approach:

• Determine the events you want to calculate the probability of.
• Starting with an initial state, iteratively add states until you obtain all end states (which represent the outcomes).
• The probability of an end state is the sum of the probabilities of each path from the initial state to this end state.
• It’s not always necessary to actually create a graph and traverse paths. You could keep track of a state’s probability while constructing the states.
  • Be careful when you do so!
• The probability of an event is the sum of the probabilities of the end states in which the event occurs.

Two sanity checks:

• The probabilities of all transitions coming out of the same state should sum to 1.
• The probabilities of all paths originating at a state should sum to 1.

If you calculate each state’s probability while consstructing the states, the sanity checks become:

• The sum of the probabilities of a state’s children divided by the probability of the state itself should equal to 1.
• The sum of the probabilities of all end states reachable from a state divided by the probability of the state itself should equal to 1.

A more advanced use this approach can be found in my article about the probabilities of battle outcomes in the board game RISK.

I’m currently working on an article that dials this approach to 11 to calculate probabilities for drawing cards in RISK. Stay tuned!