$\lim_{n \to \infty} {\mathbb E}X_n$ for a coin flipping payoff problem Suppose we have a fair coin and we start with a base amount of money $X_0 = C \in {\mathbb N}$, and each time we flip the coin we have $X_{n+1} = X_n + 1$ if the flip is heads, otherwise $X_{n+1} = 1/X_n$ if tails. Can we compute $\lim_{n \to \infty} {\mathbb E}X_n$? It seems like the limit should exist and be finite. However coming up with a formula or recurrence relation for ${\mathbb E}X_n$ seems pretty daunting after some thought. However maybe the limit can be found and proved without that explicit formula? If the limit cannot be computed explicitly, can it be related to some other limit, and/or bounded with some good bounds, and/or proved for example to be irrational?
 A: At first, we can suppose that there are some continuous probability density function  $\mu$ on $[0,\infty)$  such that $$\lim_{n\rightarrow\infty}{\mathbb P}(a\le X_n\le b)=\int_a^b\mu(x)dx$$
But there are not. That's why :
$${\mathbb P}(a\le X_n\le b)=\frac{1}{2}{\mathbb P}(a-1\le X_{n-1}\le b-1)+\frac{1}{2}{\mathbb P}(\frac{1}{b}\le X_n\le \frac{1}{a})$$
By taking limits when $n\rightarrow\infty$
$$2\int_a^b\mu(x)dx=\int_{a-1}^{b-1}\mu(x)dx+\int_{\frac{1}{b}}^\frac{1}{a}\mu(x)dx$$
By taking limits when $a\rightarrow b$ and using the fact that $\mu$ is continuous, we get :
$$2\mu(b)=\mu(b-1)+\frac{1}{b^2}\mu\left(\frac{1}{b}\right)$$
Knowing that $\mu(x)=0$ for $x<0$, we get
$$x<1\Rightarrow \mu(x)=\frac{1}{2x^2}\mu\left(\frac{1}{x}\right)$$
$$x\ge 1\Rightarrow \mu(x)=\frac{1}{2}\mu(x-1)+\frac{1}{4}\mu\left(x\right)=\frac{2}{3}\mu(x-1)$$
$$\mu(0)=\lim_{n\rightarrow\infty}\mu\left(\frac{1}{n}\right)=\lim_{n\rightarrow\infty}\frac{n^2}{2}\mu(n)=\lim_{n\rightarrow\infty}\frac{n^2.2^n}{2.3^n}\mu(1)=0$$
If $\mu(x)=0$, $\mu(x+1)=0$ and $\mu(\frac{1}{x})=0$ . But this two operations can be used to build all rationals numbers from $1$. $\mu(0)=0$ implies $\mu(1)=0$, and so $\mu(r)=0$ for all $r\in\mathbb Q$. By continuity, $\mu(x)=0$ for all $x$, so $\mu$ is not a PDF.

Let's try another method ! Consider the Stern-Brocot tree. It contains all rationals numbers. Any rational number $r$ in the tree will define an smallest open segment $(a_r,b_r)\subset\mathbb Q$ such that 


*

*For all rational $s$, ($s$ have $r$ as an ancestor in the tree) is equivalent to $s\in(a_r,b_r)$

*$a_r$ and $b_r$ are rationals and are ancestors of $r$ except if $r$ is an integer (in which case $b_r=\infty$) or $r=\frac{1}{n}$ (in which case $a_r=0$)

*Both $a_r$ and $b_r$ are greater than $1$ or lower than $1$ at the same time for $r\neq 1$.


If $r$ lies on the tree on level $p$, then $r+1$ lies on level $p+1$ and $\frac{1}{r}$ lies on level $p$. (the level is the size of the path from $r$ to the root of the tree $1$)
So each time that we obtain $X_{n+1}$ from $X_n$ there is a probability $\frac{1}{2}$ that the level increases by one. So it eventually goes to infinity. Hence
$$\forall r\in\mathbb Q\quad \lim_{n\rightarrow\infty}\mathbb P(X_n=r)=0$$
However for any $r\in\mathbb Q$, we can easily compute (we name it $p_r$)
$$\lim_{n\rightarrow\infty}\mathbb P(a_r<X_n<b_r)=p_r$$


*

*if $r< 1$
$$p_r=\frac{1}{2}p_{\frac{1}{r}}$$

*if $r>1$
$$p_r=\frac{1}{2}p_{r-1}+\frac{1}{2}p_{\frac{1}{r}}=\frac{2}{3}p_{r-1}$$

*As $(a_1,b_1)=(0,\infty)$ $$p_1=1$$

*For any rational $r>0$, after a finite number of applying $x\mapsto x-1$ (if $x>1$) and $x\mapsto\frac{1}{x}$ if $x<1$, you finally get $1$.


So you can compute any limit probability on the segments.
$$
\begin{array}{|c|c|c|}
\hline
r & (a_r,b_r) & p_r \\\hline
1 & (0,\infty) & 1 \\\hline
2 & (1,\infty) & \frac{2}{3} \\\hline
\frac{1}{2} & (0,1) & \frac{1}{3} \\\hline
3 & (2,\infty) & \frac{4}{9} \\\hline
\frac{3}{2} & (1,2) & \frac{2}{9} \\\hline
\frac{2}{3} & (\frac{1}{2},1) & \frac{1}{9} \\\hline
\frac{1}{3} & (0,\frac{1}{2}) & \frac{2}{9} \\\hline
\end{array}
$$
By previous properties and properties of the SB tree, you can deduce that :
$$\alpha=\lim_{n\rightarrow\infty}E(X_n)=\frac{1}{3}\lim_{n\rightarrow\infty}E(X_n|X_n<1)+\frac{2}{3}\lim_{n\rightarrow\infty}E(X_n|X_n>1)$$
But as $\lim_{n\rightarrow\infty}E(X_n|X_n>1)=\alpha+1$
$$\alpha=2+\lim_{n\rightarrow\infty}E(X_n|X_n<1)$$
And $\lim_{n\rightarrow\infty}E(X_n|X_n<1)$ can be bounded by dividing $(0,1)$ into more and more $(a_r,b_r)$, computing $p_r$...
If found that $$\alpha\approx 2.42683...$$
A: Assuming that $E(X_n)$ has a finite limit $a$, a lower bound is easily obtained. By conditioning,
$E(X_{n+1})=0.5E(X_n+1)+0.5E(1/X_n)$.
Letting $n$ tend to infinity and using Jensen's inequality, we get
$a\geq 0.5(a+1)+0.5/a$.
Solving a quadratic equation gives $a\geq  0.5+\sqrt{1.25}\approx 1.618$.
A: Not an answer to your question, but hopefully some reasoning that helps get there:
Fixing $X_0=1$ and running a quick simulation to calculate $\mathbb{E}(X_n)$ exactly for $n=1,2,3,4$ gives the $\mathbb{E}(X_n)=1.5, 1.625, 1.791\overline{6}, 1.911458\overline{3}$, and $\mathbb{E}(X_{25})\approx 2.4209$ and $\mathbb{E}(X_{30})\approx 2.4248$. Which makes me believe it converges to a finite number at least.
For any $k\in\mathbb{N}$, both $k+1$ and $1/k$ are rational, and $\forall q\in\mathbb{Q}$, $q+1$ and $1/q$ are rational. So it seems like $X_n$ can only take on rational values if $X_0$ is required to be a natural number. So our state space is the set of rational numbers, and we have a Markov chain, $X_n$.
The (infinite) matrix $T$ of transition probabilities is composed of rows which are all zeros except for at two column locations: $q$ goes to $q+1$ and $1/q$ with probability $1/2$ each. Each column should be zero except for in two row locations where it is 0.5 as well since only $q-1$ and $1/q$ can become $q$ in the next step. 
Can we find a discrete limiting distribution $\mu$ on $\mathbb{Q}$ such that $\mu=\mu T$? My intuition tells me "yes", but I do not know for certain as I'm quite rusty on the theory. I don't think it is irreducible. For example, how do you get $1$ in a finite number of steps from $5/4$ using only the 'flip' and 'plus one' operations? For this reason, the answer to your question will depend on your initial value. (Edit: it seems that it doesn't depend on the initial value.)
If a stationary distribution $\mu$ exists, then $$\displaystyle\lim_{n\rightarrow\infty}\mathbb{E}(X_n|X_0=1)=\sum_{q\in\mathbb{Q}} q \cdot \mu\left(q\right).$$
Now for any fixed finite $n$, $\mu_n$ will be a discrete distribution on a finite collection rational numbers. Each individual outcome will have a probability equal to $\frac{1}{2^n}$ times some natural number depending on how many ways $X_n$ can get there. Define $\mathbb{Q}_1=\{1,2\}$ and $\mathbb{Q}_{n+1}=\{\mathbb{Q}_n+1\}\cup\{1/\mathbb{Q}_n\}$.
Let $a^{(n)}_j \in \mathbb{N}$ be the number of ways $q_j$ can be reached by $X_n$ starting from $X_0=1$. Each $a^{(n)}_j \leq n$ certainly. We have
$$\displaystyle \mathbb{E}(X_n|X_0=1)=
\sum_{q_j\in\mathbb{Q_n}} q_j P(X_n=q_j|X_0=1)=
\sum_{q_j\in\mathbb{Q_n}} q_j \frac{a^{(n)}_j}{2^n}.$$
It's really tempting for me to think this converges to a rational number, but I can't say for sure as sequences of rational numbers can converge to irrational numbers. I don't have a formula for the $a^{(n)}_j$ coefficients, and it might be tough to come up with one. There are definitely some patterns to exploit though such as for $X_n$, there is one way to get 1, $n-1$ ways to get 2, $n-2$ ways to get 3, ..., and 1 way each to get $n$ and $n+1$. There seems to be some patterns with the fractional values for $X_n$ and their counts as well.
Edit: It seems that $\#|\mathbb{Q}_n|=f_{n+2}-1$ where $f_{n}$ is the $n^{th}$ Fibonacci number. I worked this out by building $\mathbb{Q}_n$ via a tree diagram. I think this approach may likely yield a formula for the $a^{(n)}_j$ coefficients and a way to delineate the elements of $\mathbb{Q}_n$.
The fibonacci numbers can be approximated by $\displaystyle f_n = \frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2^n\sqrt{5}}$ (Binet's formula). The $a^{(n)}_j$ coefficients are bounded by the size of $\mathbb{Q}_n$, and the rational number elements of $\mathbb{Q}_n$ are bounded by $n+1$. Thus
$$\displaystyle \mathbb{E}(X_n|X_0=1)=\sum_{q_j\in\mathbb{Q_n}} q_j \frac{a^{(n)}_j}{2^n} \leq (n+1) (f_{n+2}-1)^2\frac{1}{2^n}.$$
This seems to converge to zero as $n\rightarrow\infty$ (wrong! as pointed out below -- it diverges to $\infty$, so this calculation doesn't give an upper bound), so I feel I have made an error somewhere as I expected a positive upper bound. I'd love to get some insight from someone else.
