O'Reilly logo

Probability and Stochastic Processes by Ionut Florescu

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

14.5 Classical Examples of Martingale Reasoning

In this section, we present examples of using martingales to provide elegant solutions to seemingly complicated problems.

14.5.1 The expected number of tosses until a binary pattern occurs

Suppose we toss an unbalanced coin which has probability p of landing Head and probability c14-math-0319 of landing Tail. What is the expected number of tosses until a certain pattern appears for the first time?

To make the reasoning more accessible, we consider a specific pattern, say, for example, c14-math-0320. This pattern may be any sequence of heads and tails. There are other ways to find the expected number of tosses until the pattern occurs for the first time, but by far the most elegant and interesting reasoning is using martingale theory.

To perform the martingale reasoning, we need to construct a martingale. To this end, consider a game where at each step we toss this coin which has probability p of landing H. Consider a sequence of gamblers. Gambler i starts playing at toss number i, and every gambler bets on the exact pattern we want to calculate the probability for.

Specifically, in our example (c14-math-0325), gambler i bets on H at toss i.If the gambler wins, then he/she ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required