Q:

Probability to get twice as many heads as tails at some point in an infinite sequence of coin tosses

Let consider an infinite sequence of tosses of a fair coin ($p = 1/2$ to get head or tail).
What is the probability to get, at least once, twice as many head as tails?
In another words, what is the probability that, there is $n, k \in \Bbb N^*$ such as $H_{3n} = 2n, T_{3n} = n$ (where $H_n$ denote the number of heads, and $T_n$ the number for tails at the $n$)?
What I tried: I don't even know how to start... I tried a lot of things but nothing really worked...

A:

Let $X_n = H_n - 2 T_n$.   This process forms a Markov chain; the conditional probabilities for $X_n$ given $X_{n-1}$ are $1/2$ for $X_n = X_{n-1}+1$ or $X_{n-1}-2$, $0$ otherwise.
Let $u(x)$ be the probability of ever being at $0$ for this process starting at $x$ (including the starting point, so $u(0) = 1$).  Thus
$ u(x) = (u(x+1) + u(x-2))/2$ for $x \ne 0$, and you want $(u(1) + u(-2))/2$.
The recurrence $u(x) = (u(x+1) + u(x-2))/2$ has basic solutions $u(x) = r^x$ for 
$r = 1$, $(1- \sqrt{5})/2$ and $(1+\sqrt{5})/2$.  Thus for some constants $a_-, b_-, c_-, a_+, b_+, c_+$ we should have
$$ u(x) = \cases{a_- + b_- r_1^x + c_- r_2^x & if $x < 0$\cr
                 a_+ + b_+ r_1^x + c_+ r_2^x & if $x > 0$\cr}$$
Now because $|r_1^x| \to \infty$ for $x \to -\infty$ and $r_2^x \to \infty$ for $x \to +\infty$, we should have $b_- = 0$ and $c_+ = 0$.  Moreover we should have $u(x) \to 0$ for $x \to -\infty$, so $a_- = 0$.  To fit with $u(0)=1$ we should have $c_1 = 1$.  Then $a_+$ and $b_+$ are determined by $u(1) = (u(-1) + u(2))/2$ and $u(2) = (u(0)+u(3))/2$, i.e. 
$$ \eqalign{a_+ + b_+ r_1 &= (r_2^{-1} + a_+ + b_+ r_1^2)/2 \cr
            a_+ + b_+ r_1^2 &= (1 + a_+ + b_+ r_1^3)/2 \cr}$$
whose solutions are
$$ \eqalign{a_+ &= \frac{3 \sqrt{5} - 5}{2}\cr
      b_+ &= \frac{7 - 3 \sqrt{5}}{2}\cr}$$
That makes your answer $$(r_2^{-1} + a_+ + b_+ r_1)/2 = \frac{9 - 3 \sqrt{5}}{4}$$ 

A:

Probability of getting $2k$ heads and $k$ tails is $\frac1{2^{3k}}\binom{3k}{k}$. Thus the expected number of successes (getting twice as many heads as tails) is
$$
\begin{align}
\sum_{k=1}^\infty\frac1{2^{3k}}\binom{3k}{k}
&=\frac1{2\pi i}\sum_{k=1}^\infty\oint_{|z|=1^-}\left(\frac{\frac1z+z^2}2\right)^k\frac{\mathrm{d}z}z\\
&=\frac1{2\pi i}\oint_{|z|=1^-}\frac{\frac{\frac1z+z^2}2}{1-\frac{\frac1z+z^2}2}\frac{\mathrm{d}z}z\\
&=-\frac1{2\pi i}\oint_{|z|=1^-}\frac{1+z^3}{(1-z)(1-z-z^2)}\frac{\mathrm{d}z}z\\[6pt]
&=\color{#C00}{\frac{\phi^3+1}{(\phi-1)(\phi+2)}}\color{#090}{-1}\\[6pt]
&=\frac3{\sqrt5}\tag1
\end{align}
$$
Since the sum in the integral converges for $|z|\lt1$ and not for $|z|\gt1$, we integrate just inside the unit circle and therefore avoid the singularities at $z=-\phi$ and $z=1$. We catch the singularities at $\color{#C00}{z=\frac1\phi}$ and $\color{#090}{z=0}$.
Suppose that the probability of at least one success is $p$, then the probability of exactly $k$ successes is $p^k(1-p)$. Thus, the expected number of successes is
$$
\sum_{k=1}^\infty kp^k(1-p)=\frac p{1-p}\tag2
$$
Since $\frac p{1-p}=\frac3{\sqrt5}$, the probability of at least one success is
$$
\bbox[5px,border:2px solid #C0A000]{p=\frac3{3+\sqrt5}}\tag3
$$

Here is an alternate computation of $(1)$ that doesn't use contour integration.
$$
\begin{align}
\sum_{k=1}^\infty\frac1{2^{3k}}\binom{3k}{k}
&=\frac1{2\pi}\sum_{k=1}^\infty\int_0^{2\pi}\left(\frac{e^{-ix}+e^{2ix}}2\right)^k\,\mathrm{d}x\\
&=-\frac1{2\pi}\int_0^{2\pi}\frac{e^{3ix}+1}{e^{3ix}-2e^{ix}+1}\,\mathrm{d}x\\
&=-\frac1{2\pi}\int_0^{2\pi}{\scriptsize\left(\frac{10+3\sqrt5}5-\frac{\left(5+3\sqrt5\right)/5}{1-e^{-ix}/\phi}-\frac{\left(-5+3\sqrt5\right)/5}{1+e^{ix}/\phi}-\frac2{1-e^{ix}}\right)}\,\mathrm{d}x\\
&=-\left(\frac{10+3\sqrt5}5-\frac{5+3\sqrt5}5-\frac{-5+3\sqrt5}5-2\right)\\[3pt]
&=\frac3{\sqrt5}\tag4
\end{align}
$$
Note that for $|r|\lt1$
$$
\begin{align}
\frac1{2\pi}\int_0^{2\pi}\frac1{1-re^{\pm ix}}\,\mathrm{d}x
&=\frac1{2\pi}\int_0^{2\pi}\sum\limits_{k=0}^\infty r^ke^{\pm ikx}\,\mathrm{d}x\\
&=1\tag5
\end{align}
$$
and we take
$$
\begin{align}
\frac1{2\pi}\int_0^{2\pi}\frac1{1-e^{ix}}\,\mathrm{d}x
&=\lim_{r\to1^-}\frac1{2\pi}\int_0^{2\pi}\frac1{1-re^{ix}}\,\mathrm{d}x\\[3pt]
&=1\tag6
\end{align}
$$

