Prove it – Ep2: Another random walk
Let’s follow an algorithm:
- Determine heuristic used in example.
- Summarize math solution.
- Define new heuristic, if possible.
- Discuss Claude’s math solution.
- Provide dashboard solution, if possible.
Claude prompt:
You are planning to visit your friend who lives 5 blocks away. Instead of going straight there, you plan to go for a “random walk”
Every time you are at your house you leave and walk a block. At this time, you flip a coin. if it’s heads, you advance a block. if it’s tails, you return to your house. This flip happens at every block until you get to your friend’s house.
How many flips do you expect this to take?
Heuristic:
The only “edge” in this problem is the first flip, which always advances you towards your friends house. Since there are 8 total flips, 5 of them towards the friend’s house.
E[+] = 5/8*1 + 3/8*-1 = 1/4 so 16 total flips to advance 4 houses.
Mathematical solution:
E04 = 1 + E14 ;
E14 = 1 + 1/2E04 + 1/2E24
E24 = 1 + 1/2E14 + 1/2E24
E34 = 1 + 1/2E24 + 1/2E44
E04 = 4 + E24 = 9 + E34 = 16 + E44
See squares appear. This is an n-squared problem.
New heuristic
Imagine your friend lives very far away. The “edge” would disappear. To get to your friend’s house quickly, you would need every larger extreme events. Think HHHHHHH for example.
The larger the N, the larger the penalty. Guess n-squared problem. N = 4, 16 flips.
Claude math
Claude correctly identifies n-squared problem.
The trickiest part is making sure Claude understands the situation, especially that a coin flip occurs at your house, it’s just the outcome doesn’t matter there.
If the initialization isn’t correct, the problem quickly becomes different.
Efehn’s puzzles completely changed how I think—so engaging and rewarding!
Sarah Lee
Puzzle Enthusiast – Not a real person