## An army of gamblers and a martingale Start flipping a coin. How long should you wait (on average) before observing the pattern ${HHTHHTT}$ !? Easy you might say, that’s simply the hitting time of the state ${H}$ starting from state ${A}$ of the following Markov chain. Indeed, one can solve this kind of problem using a first step analysis. In other words, if ${a}$ is the expected number of steps before reaching ${H}$ starting from ${A}$, ${b}$ is the expected number of steps before reaching ${H}$ starting from ${B}$, ${c}$ is the expected number of steps before reaching ${H}$ starting from ${C}$, etc… one can readily see that ${a,b, \ldots, h}$ verify the system of equations $\displaystyle \begin{array}{rcl} a &=& 1 + \frac12(a+b), \quad b = 1 + \frac12(a+c), \quad c = 1 + \frac12(c+d) \\ d &=& 1 + \frac12(a+e), \quad e = 1 + \frac12(a+f), \quad f = 1 + \frac12(c+g) \\ g &=& 1 + \frac12(e+h), \quad h = 0. \end{array}$

After a finite amount of time and coffee one then come up with the answer ${a=128}$. That was a little bit tedious and I don’t really want to know how long one should wait on average before observing the sequence ${HHTHTTTHTHHHHTTHTHTTH}$.

It turns out that there is a very neat way to approach this kind of problems without solving any linear system. Apparently, this trick was discovered in the 80s by Shuo-Yen Robert Li. As often in probability, this boils down to introducing a clever martingale. Suppose that one wants to know how long it takes on average before observing the magic coin pattern ${x_1x_2 \ldots x_n}$ of length ${n \geq 1}$ with ${x_i \in \{H,T\}}$ for all ${1 \leq i \leq n}$. To this end, one will introduce an army of gamblers, a casino, a game of chance and a martingale. The martingale ${M}$ describes the amount of money earned by the casino. At each round (starting at round ${t=1}$) the casino tosses a coin and the gamblers can make bets. If a gambler starts betting just before round ${k}$, he wins if the coin shows ${x_1}$. If he decides to bet again at round ${k+1}$, he wins if the coin shows ${x_2}$, etc… Suppose that there are infinitely many gamblers ${G_0, G_1, G_2, \ldots}$ and that gambler ${G_k}$ starts betting just before round ${k+1}$. The game is fair in the sense that if a gambler bets an amount ${A}$, with probability ${1/2}$ he gets ${2A}$ and with probability ${1/2}$ he losses his bet. One supposes that gambler ${G_k}$ starts betting ${1}$ dollar just before round ${k+1}$ and keeps reinvesting his total capital until he either losses everything (total loss equals ${1}$ dollar) or observes the magic coin pattern ${x_1x_2 \ldots x_n}$ (total earning equals ${2^n-1}$). Indeed, the amount of money earned by the casino is a martingale and ${M_0=0}$. For example, ${M_1=1}$ if the first gambler ${G_0}$ loses his bet and ${M_1=-1}$ if the wins. Consider the time ${\tau}$ when the magic coin pattern first appears. This is a stopping time and the optional stopping theorem for martingales shows that ${\mathbb{E}[M_{\tau}] = 0}$. Indeed, one can also compute this quantity another way. By time ${\tau}$, all the losers have given ${1}$ dollar to the casino. Also, if the gambler ${G_k}$ is still in the game he has won a total amount ${2^{\tau-k}-1}$. in other words, $\displaystyle M_{\tau} = \tau - \sum_{j=0}^{\tau-1} 2^{\tau-k} \, \delta_j$

where ${\delta_j=1}$ if the gambler ${G_j}$ is still in the game after the round ${\tau}$ and ${\delta_j=0}$ otherwise. The fundamental remark is that the quantity ${\sum_{j=1}^{\tau} 2^{\tau-k+1} \, \delta_j}$ is not random so that ${\mathbb{E}[\tau] = \sum_{j=0}^{\tau-1} 2^{\tau-k} \, \delta_j}$. Indeed, right after round ${\tau}$ one can know with certainty whether ${G_{k}}$ is still in the game or not. Gambler ${G_{\tau-k}}$ is in the game only if the ${k}$ last letters of the magic word ${x_1x_2 \ldots x_n}$ are the same as the first ${k}$ letters. For example, if the magic word is ${HHTHHTH}$ then the gamblers who have seen the pattern ${H}$, ${HHTH}$ and ${HHTHHTH}$ at time ${\tau}$ are still in the game when the magic word first appear. In this case this shows that ${\mathbb{E}[\tau] = 2^1+2^4+2^7}$. For example, this immediately shows that we have to wait on average ${2^{21}+2^1}$ coin tosses before observing the pattern ${HHTHTTTHTHHHHTTHTHTTH}$.

1. #### how i quit gambling said,

April 14, 2013 at 8:45 pm

hi, you do had a great site, thank for sharing these valuable information.

2. #### how i quit gambling said,

April 17, 2013 at 6:57 pm

Hello, This is a nice information, thanks.

3. #### 一部予約販売 安心の正規品 said,

November 20, 2015 at 2:59 am

常に と同様 記事やレビュー内容記事私は小さい読み取るために使用される彼らの動機をクリアし、それがまた起こっていますこの時点で私が読んでいるこれで。
一部予約販売 安心の正規品 http://www.vietnamtoday.vn

4. #### 一部予約販売 大人可愛い2015新作 said,

November 20, 2015 at 3:05 am

利用での作業 あなたがしている | プラットフォームシステム何のブログを見つけるために好奇心が強い| 私は私は？ サイトブログ |セキュリティ私の最新問題の問題 |いくつかの小さなマイナー | 持つ経験と私は思います私は今|リスクフリーもっと何か固定します。 あなたがいずれかを持っていますか？
一部予約販売 大人可愛い2015新作 http://djsantoslive.com