Today we'll try to unpack a general strategy for working on probability problems, specifically ones where many events happen in sequence. Or you can decide to go straight to the challenge.
Here's the strategy:
Instead of thinking about a series of probabilistic events happening to one agent or object, imagine dozens or even thousands of agents and apply the probabilities of different events as a ratio to figure out how many agents you can expect to have each possible sequence of experiences.
The number of agents that have some specific experience, divided by the total number of agents, is the probability that a single agent will have that experience.
This problem-solving strategy doesn't eliminate the mathematical steps of solving probability problems, but it will let you work with whole numbers instead of fractions. Just be sure to pick a large enough number of agents that you don't have to deal with one-third of one agent having one experience while the other two-thirds of the agent has another. In this problem, using an initial number of agents that's a large power of two is particularly effective, since we repeatedly split this group in half.
In today's challenge, a hopping robot moves between several dots that are colored, not numbered. But let's assign each dot a number to make it easier to talk about the robot's motion.
Also, while there are only nine dots in this image, you can imagine that the row goes out forever in both directions and that the numbering keeps up accordingly. Now let's look for some patterns in how the robot moves.
We can think of hopping one dot to the right as adding to the robot's position, while a move to the left is subtracting For example, the sequence left, right, left, left would put the robot at dot
One important observation that we can support with this arithmetic perspective is that the number of hops left vs. the number of hops right is all that you need to know to determine the robot's final position. The order in which the robot makes those hops doesn't matter at all in determining the robot's final destination. For example, the sequence left, left, left, right would also put the robot at dot This observation can definitely help you solve today's challenge efficiently.
However, what if we don't just care about the robot's destination, what if we care about what dots it visits en-route? One interesting and challenging behavior that we can study is the chance a randomly hopping robot has of returning to dot at least once in the middle of its hopping sequence. As a warm-up to today's challenge, let's look at a robot that makes a six-hop journey.
So that we don't have to talk about everything in terms of fractions, let's think about starting with robots at dot and study what happens if, at each chance they are given to hop, half of the robots on each dot hop one dot left and the other half hop one dot right. Additionally, if a robot ever returns to dot we'll "recapture" it, stop tracking its movement, and add it to the tally in the second-to-lowest row of the chart below. This will ensure that we don't count one robot that returns to twice as if it was two robots, each returning to once.
Although... If we wanted to start a "tag and release" program, we could use a three-dimensional chart to track robots that are captured at multiple times.
Here's the distribution of robots on each dot if you track each of robots for either hops or until it's recaptured at dot
|Total count recaptured at|
|Total count still wandering:|
So, after up to hops, out of robots will have been recaptured at and only of the robots will remain wandering.
Correspondingly, that means the chance of any individual robot returning at least once to over the course of a -hop journey is If you want to explore this more, try using a spreadsheet or write a program that shows what happens when you let loose thousands or tens of thousands of robots and let them wander for dozens or hundreds of hops.
In today's challenge, the robot doesn't get captured on any dot, but you can use a similar chart to figure out the chance of a robot ending a four-hop journey on either or