One very common type of questions in Quant interviews is Random Walks. In this post, we will start with a simple example of a random walk question and gradually will generalize it, also discussing possible variations.

Problem: Two tennis players, A and B, are at deuce (40-40) during a game of a tennis match. If A is serving and has a 60% probability to win a point, what is the probability that he wins the game?

Remark: The game is won when one of the two players gets a 2-point lead.

SOLUTION

Let us denote by P the probability that A wins the game. There are three possibilities after playing the next 2 points in the game:

A wins both points and the game. The probability for this is 60% × 60% = 36%.

B wins both points and the game. The probability for this is 40% × 40% = 16%.

A and B win one point each and they are at the same place they started from. The probability for this is 100% – 36% – 16% = 48%.

Therefore, we can set the equation:

P = 0.36+0.48P \implies 0.52P=0.36 \implies P=9/13 \sim 69\%

Remark: Another approach for solving the problem above is computing the probabilities for A winning the game after 2 points (48%), 4 points (36% × 48%), 6 points (36% × 36% × 48%), etc, and summing them up using the geometric progression formula. However, the recursive approach above is usually the shorter and better choice in problems like this one.

Now, we rephrase the problem above in terms of random walks:

then what is the probability that X is equal to 2 before X is equal to -2?

Clearly, changing the 60% probability to another number will not complicate the calculations in any way. What if we change the step sizes and the boundary conditions though? Next, we discuss the following generalized version of the problem:

Problem: Let X be a stochastic process. If

P(X_{n+1} = X_n + a) = p, \quad P(X_{n+1} = X_n - b) = 1-p, \quad X_0=0,

then what is the probability that X becomes less or equal to U before X gets larger or equal to V, where U < 0 < V?

SOLUTION

Let P(i) be the probability that X becomes larger or equal to V before it gets smaller or equal U, if currently X=i. We can write the recursive formula:

P(i)=pP(i+a)+(1-p)P(i-b)

with the boundary conditions

P(i)=0 \text{ for } i\in \{U-b+1,\cdots,U\}, \quad P(i)=1 \text{ for } i\in \{V, \cdots , V+a -1\}.

The recursive formula is linear and therefore its general solution can be found by finding the roots x_1, x_2, \cdots , x_{a+b} of the polynomial

R(x)=px^{a+b}-x^b+(1-p)=0,

and then setting

P(i)=\sum_{j=1}^{a+b}c_jx^{i}_j

for some parameters c_1, c_2, \cdots , c_{a+b}.

We get a linear system of a+b equations (the boundary conditions) and a+b unknowns (the coefficients of R(x)) which can be solved to find the explicit formula for P(i).

Remark: It is possible that one of the boundaries U and V is \pm \infty. In this case, some of the boundary conditions will get the form \lim_{i\to-\infty}P(i)=0 or \lim_{i\to\infty}P(i)=1.

While the approach above usually works for variations of the problem given on interviews, it is worth noting that when the polynomial R(x)=px^{a+b}-x^b+(1-p) is of high degree, it is possible that its roots can not be explicitly computed. An alternative approach, while still computationally demanding, would be to solve directly the linear system given by

P(i)=pP(i+a)+(1-p)P(i-b)

and the boundary conditions

P(i)=0 \text{ for } i\in \{U-b+1,\cdots,U\}, \quad P(i)=1 \text{ for } i\in \{V, \cdots , V+a -1\}.

We demonstrate this with a simple example.

Problem: You start with $20 and keep betting $1. What is the probability that you will get broke before you win $50? What is the expected number of bets until one of these two events occurs?

SOLUTION

Using the recursive formula and the boundary conditions derived above, we get the following linear system:

Therefore, the probability that you will get broke before you win \$50, if you start with \$ 20, is equal to P(20)=(50-20)/50=60\%. Of course, if we could make the hypothesis that this is the explicit formula for P(i), we could also simply check it satisfies the recursive formula by plugging it there.

Finding the expected number of bets can be done similarly. If we denote by Q(i) the expected number of bets until you get to $0 or $50, starting from $i, we get the following recursive formula:

Q(i)=1+(Q(i-1)+Q(i+1))/2 \text{ for } 1\leq i \leq 50, \quad Q(0)=Q(50)=0.

We can express these relations via the linear system:

Therefore, the expected number of bets until you broke or win $50 is equal to Q(20)=(50-20)/50=60\%. Once again, if we could guess the general formula for Q(i), we could plug it in the relation and verify it is indeed correct.

Finally, we present another elegant solution to the last problem that involves stochastic processes.

SOLUTION

We note that the stochastic process X(t) defined by the amount of money you possess at time t \in \mathbb{N}_0 is a martingale. Indeed, \mathbb{E}(X(t+1)|X(1), \cdots , X(t))=X(t), and therefore \mathbb{E}(X(t)) = 20 for every t \in \mathbb{N}.

Blaž Urban Gracar is a Slovenian artist. He is a musician (composing music for the theater, producing left-field electronica, playing keyboards in a rock band), writer (publishing poetry, prose and comic books), filmmaker (editing and animating short films), and game designer (mostly creating puzzly solo games). He lives by the sea with his partner, her daughter, two cats, a dog and a turtle.

Interview

Q. Hello, Blaž!

A. Hi, Puzzle Prime! Thanks for featuring me.

Q. I know you are quite a busy person, I’m glad to have you here.

A. Yes, ????????, + I also make music, which is basically my main source of income. I make strange electronic music, play keyboards in a rock band and compose music for films and theater. Besides music and game-making, I also write – I have published a few books – and I make videos. Lately this means making animated shorts, but I graduated as a film editor, so I have made or collaborated on several films.

Q. Sounds great! I would first like to focus on your puzzles though, specifically your first published book, LOK.What was the inspiration behind it?

A. When I was making my previous puzzle book, Lineon, which is sadly still unfinished, I started corresponding with Stephen Lavelle, better known as Increpare, who made a bunch of great and acclaimed puzzle games, among them Stephen’s Sausage Roll, which is praised as one of the best puzzle games of all time. I sent him Lineon and he responded with a set of paper puzzles of his own, which were word-search puzzles using the Toki Pona language. Toki Pona is a constructed language that I don’t understand, so solving these puzzles felt very other-wordly. I started thinking how would such word-searches work if they used a completely made up set of words, which would have meaning only inside these puzzles. If we say “Apple” for example, we mean a red and round fruit. What if a word like “Lok” meant that you could erase a letter and that’s it? This idea felt very interesting to me and I quickly prototyped a puzzle which already used a lot of words that are present in the final book. It then took me about a year before I returned to this idea and saw potential for something greater.

Q. How long did it take you to finish LOK and what was the hardest part?

A. It took me a little more than 6 months to make LOK. I thought it would take me maybe 3 months, as I saw LOK as a smaller project at first, something to make in between bigger projects, so I pushed to finish it as soon as possible and made the first draft in about 2 months. I now see this as a smart approach – to rush the first draft – as it then took me 4 more months to perfect everything and make it really shine. I think it’s really important to have everything in place and see it for what it is, even if it’s not finely tuned yet. The last 10% were the hardest, but this was expected. It took me weeks to decide on some miniature details, like the correct font for titles, or the alignment of chapter artworks. Everything needed to match the vision, and it was hard to be certain what is correct in some aspects. But I’m very happy with how it all came together in the end.

Q. How do you approach making a puzzle?

A. Well, apart from some rare tributes and try-outs of some already established genres, I generally like to make up my own system of rules, within which I then create a bunch of puzzles. I rarely do one-offs. So, when I first start exploring a new system I made up, I just throw things at the wall and see what sticks. These puzzles are usually ugly, random and without any real a-ha moments, but with them, I kind of expose most of everything that the system is capable of. I then re-do the puzzles that have interesting interactions or ideas, try to make them more elegant, guided and beautiful, but I also retain some of these early puzzles as they were, because they already work quite fine. So, after I internalize all the ins and outs of a system and start working on proper puzzles, my process is usually thinking of an idea that I would like the solver to find out and then kind of build a pathway for them. I try to think like the solver and how they would react to certain insights and deductions. Basically, I want the solver to have fun and to blow his mind every few puzzles, haha.

Q. How does creating puzzles differ from creating in these other fields?

A. Music, films, prose, all of these art forms are kind of direct compared to puzzle-making. They communicate something in a direct way, even if they are metaphorical or dream-like. Puzzles, on the other hand, work on two levels. One is the first impression: how they look at first sight, if they are symmetrical, big or small, if they intimidate or seem easy. The second level is the hidden meaning of a puzzle, its solution and how you get to it. It feels like designing an onion, where you want to put as many surprises into different layers as possible. You also need to be a lot kinder to the consumer of your puzzles compared to other art forms. You have to respect their intelligence and patience, make the system and a puzzle as mechanically sturdy as possible, because ultimately they need to “get” your message. You certainly need to be a lot more pragmatic.

Q. You come from Slovenia. Is there an active puzzle scene in Slovenia and do you hang out with other puzzle designers?

A. There is no puzzle scene in Slovenia that I know of. It’s strange, because ever since I got serious about game design, I feel like I create in a bubble. When I make music, people around me respond to it, they come to concerts, they buy CDs. Even my books, which are a bit more niche, find some audience in Slovenia. But my games or puzzles don’t really connect with anyone around me. It’s like I live a double life, one with friends and family, and the other just on the computer, which I use to communicate with puzzle lovers from around the world. This is how I got in touch with you as well. When I published LOK, I sold 95% of books to people outside of Slovenia, people I don’t know, people from Europe, America, Asia. It’s strange, but it also feels nice to at least have an audience somewhere, even for my small and weird little games.

Q. What are your next puzzle projects?

A. Based on the response for LOK, I already have many ideas for the continuation of the LOK story. I don’t want to say too much, but I’ve had talks with Raindrinker, a talented creator from Spain I met online, about a possible collaboration in making something LOK-like. Besides LOK, I might return to Lineon and start working on it again from the ground up, with the experience I gained in the meantime. There are some other ideas that I’m bouncing around in my head, maybe also a continuation of my solo card game “All Is Bomb” in some form. Let’s see what happens – I love designing games, so something will probably appear in a short while.

Since 2018, Catriona Shearer, a UK teacher, has been posting on her Twitter various colorful geometry puzzles. In this mini-course, we cover 12 of her problems and use various techniques, such as metrics, constructions, and trigonometry, to solve them.

Please note:
This action will also remove this member from your connections and send a report to the site admin.
Please allow a few minutes for this process to complete.