Pharaoh: Random Walks

I’ve recently been playing a bit of Pharaoh, an old city-building game in which you cultivate an ancient Egyptian civilisation.

In order to attract skilled and wealthy citizens to your settlement, it is necessary to construct neighbourhoods with access to various goods and services. Examples include food, water, healthcare, access to religious facilities, and (crucially) beer.

pharaohWhether or not a particular building has access to a given service is determined by whether it is regularly visited by the associated worker. For example, a trader from the bazaar will roam the neighbourhood, delivering food to any house she crosses.

However, these workers do not wander purposefully; a bazaar trader will not seek out houses, nor will she avoid those she has already delivered food to. She will instead execute something of a random walk, constrained to the roads connecting the bazaar to the houses.

This stochastic behaviour means that junctions tend to decrease the efficacy of your workers; the greater the number of forks in the road, the greater the number of opportunities for the bazaar worker to get lost. She may end up missing a house, passing the same house twice, or walking into an industrial district!

So let’s say you have a bazaar at one end of a road and a house at the other, and some network of roads in-between the two. What is the probability of the trader reaching the house? In this post, we’ll look at a particular family of road networks and see if we can come up with a generic expression for the probability of traversing a member of it.

In the following, we’ll make a few assumptions (which are not necessarily reflected in the actual mechanics of Pharaoh):

  • on reaching an n-way intersection, the trader chooses any one of the branches with equal probability 1/(n – 1), excluding the branch on which she approached, which she chooses with probability 0;
  • the trader will wander forever until she reaches either the house or the bazaar, at which point she will stop.

Let’s get started!

\

Single T-junction

In this first case, we have a single road connecting the bazaar and the house with a single three-way junction somewhere along its length. We will assume that nothing special lies at the end of the branching road, so that, if the trader reaches the end of it, she will simply turn around and walk back towards the junction.

road1For brevity, we will call the road segments 1, 2 and a, as shown in the diagram.

The case of a single T-junction is simple, in that the trader can only take a finite number of paths before stopping. There are only two ways she can reach the house:

  1. walk along 1 and reach the junction; choose 2 with probability 1/2; walk along 2 and reach the house;
  2. walk along 1 and reach the junction; choose a with probability 1/2; walk along a and reach the dead end; walk back along a and reach the junction; choose 2 with probability 1/2; walk along 2 and reach the house.

We can denote the paths above with the following condensed notation:

  1. 12
  2. 1aa2

It is fairly easy to see that the total probability of the trader reaching the house is

\displaystyle p(1)=\frac{1}{2}+\frac{1}{2}\times\frac{1}{2};

\displaystyle p(1)=\frac{3}{4}.

The first term is the probability of the trader going straight across the junction, the second the probability of her being diverted by the junction, but choosing the correct path the second time she encounters it.

\

Double T-junction

road2Let’s now look at a single road with two three-way junctions on it. The road segments are now called 1, 2, 3, a and b. Here are some of the simplest paths that take the trader to the house:

  1. 123
  2. 1aa23
  3. 12bb3
  4. 1aa2bb3
  5. 12bb2aa23
  6. 1aa2bb2aa23
  7. 1aa2bb2aa2bb3

You can see things are now substantially more complicated. With the introduction of this single additional junction, the trader is suddenly able to take infinitely many paths, since she can spend as much time as she likes moving back and forth between the two junctions before finally committing to the road toward the house.

Rather than writing out an exhaustive list of all possible routes the trader can take, it is much easier to evaluate p(2) by recycling our result for the single T-junction. We established that the total probability of the trader passing through a T-junction was 3/4. For simplicity, then, let’s replace our junctions with little black boxes, which allow the trader through with probability 3/4 and send her back with probability 1/4.

What now are the possible (simplified) paths? The trader can:

  1. Pass straight through both black boxes, each with probability 3/4;
  2. Pass through the first black box with probability 3/4; be reversed by the second black box with probability 1/4; be reversed by the first black box with probability 1/4; pass through the second black box with probability 3/4.

In the third path, the trader is turned around four times, in the fourth path six, and so on. The total probability of her reaching the house is thus

\displaystyle p(2)=\frac{3}{4}\times\frac{3}{4}+\frac{3}{4}\times\frac{1}{4}\times\frac{1}{4}\times\frac{3}{4}+\frac{3}{4}\times\frac{1}{4}\times\frac{1}{4}\times\frac{1}{4}\times\frac{1}{4}\times\frac{3}{4}+...;

\displaystyle p(2)=\left(\frac{3}{4}\right)^2\left(1+\frac{1}{16}+\frac{1}{16^2}+...\right).

The infinite geometric series is not too hard to evaluate in general:

\sigma(\beta)=1+\beta+\beta^2+...;

\beta\sigma(\beta)=\beta+\beta^2+\beta^3+...=\sigma(\beta)-1;

1=(1-\beta)\sigma(\beta);

\displaystyle \sigma(\beta)=\frac{1}{1-\beta};

\displaystyle \sigma(1/16)=\frac{1}{1-\frac{1}{16}}=\frac{16}{15}.

Hence

\displaystyle p(2)=\frac{9}{16}\times\frac{16}{15};

\displaystyle p(2)=\frac{3}{5}.

So the trader’s chances of reaching the house are reduced a little by the introduction of the extra junction. Let’s go further!

\

Triple T-junction

road3I won’t bother writing out the possible paths this time; you can easily imagine the complicated paths the trader can take. We’ll play the same trick as before, and draw a black box around the first two junctions, which we have already established allow the trader to pass with probability 3/5, and one around the third junction, which allows her through with probability 3/4. The logic is very much like that in the preceding case:

\displaystyle p(3)=\frac{3}{5}\times\frac{3}{4}+\frac{3}{5}\times\frac{1}{4}\times\frac{2}{5}\times\frac{3}{4}+\frac{3}{5}\times\frac{1}{4}\times\frac{2}{5}\times\frac{1}{4}\times\frac{2}{5}\times\frac{3}{4}+...;

\displaystyle p(3)=\frac{3}{5}\frac{3}{4}\left(1+\frac{1}{10}+\frac{1}{10^2}+...\right);

\displaystyle p(3)=\frac{9}{20}\times\frac{10}{9};

\displaystyle p(3)=\frac{1}{2}.

Nice! So, after adding and multiplying all of those factors of 1/2 behind the scenes, we end up with 1/2 again!

You might have noticed a pattern starting to unfold here:

\displaystyle p(1)=\frac{3}{4};

\displaystyle p(2)=\frac{3}{5};

\displaystyle p(3)=\frac{1}{2}=\frac{3}{6}.

This progression is strongly suggestive of the following general expression:

\displaystyle p(n)=\frac{3}{3+n}.

How can we prove our conjecture? By induction, as we’ll see in the next section.

\

n T-junctions

road4Let’s start by assuming that the probability of the trader passing through a series of n junctions is indeed 3/(3+n). We want to show that, if this assumption is true, it necessarily follows that the probability of the trader passing through n+1 junctions is 3/(3+(n+1)): this is the basis of proof by induction.

We proceed as we have done in the last two cases: we put a black box around the first n junctions, and a second black box around the additional junction. The probability of the trader passing through the first black box is 3/(3+n), so the probability of her being reversed by the same black box is 1 – 3/(3+n) = n/(3+n). Hence, the probability of her passing through n+1 T-junctions is

\displaystyle p(n+1)=\frac{3}{3+n}\times\frac{3}{4}+\frac{3}{3+n}\times\frac{1}{4}\times\frac{n}{3+n}\times\frac{3}{4}+\frac{3}{3+n}\times\frac{1}{4}\times\frac{n}{3+n}\times\frac{1}{4}\times\frac{n}{3+n}\times\frac{3}{4}+...;

\displaystyle p(n+1)=\frac{3}{3+n}\frac{3}{4}\frac{1}{1-\frac{1}{4}\frac{n}{3+n}};

\displaystyle p(n+1)=\frac{3}{3+n}\frac{3}{4}\frac{3+n}{3+n-\frac{1}{4}n};

\displaystyle p(n+1)=3\frac{3}{4}\frac{1}{3+\frac{3}{4}n};

\displaystyle p(n+1)=3\frac{1}{4+n};

\displaystyle p(n+1)=\frac{3}{3+(n+1)}.

Bingo! With this result, we have shown that:

  • if p(0)=1, p(1)=\frac{3}{4};
  • if p(1)=\frac{3}{4}, p(2)=\frac{3}{5};
  • if p(2)=\frac{3}{5}, p(3)=\frac{3}{6};

and so on and so forth. The final step in the proof is to show that p(0) is indeed 1; if we can do that, the probability for every other value of n follows automatically from the above! Happily, that p(0)=1 is obviously true, because if there are no junctions in the trader’s way, she is guaranteed to reach the house. Therefore we can state categorically that the probability of the trader reaching the house separated from the bazaar by n three-way junctions is

\displaystyle p(n)=\frac{3}{3+n}.

\

This result is just the tip of the iceberg. You can easily imagine more complex road networks between the bazaar and the house containing (say) four-way junctions, loops, branches with branches, and so on. Try analysing some for yourself: maybe you’ll discover some elegant equations of your own!

Return to top

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s