$\lim_{n \to \infty} {\mathbb E}X_n$ for a coin flipping payoff problem

Question

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?

Answer 1

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

1. For all rational $s$, ($s$ have $r$ as an ancestor in the tree) is equivalent to $s\in(a_r,b_r)$
2. $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$)
3. 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$$

1. if $r< 1$ $$p_r=\frac{1}{2}p_{\frac{1}{r}}$$
2. if $r>1$ $$p_r=\frac{1}{2}p_{r-1}+\frac{1}{2}p_{\frac{1}{r}}=\frac{2}{3}p_{r-1}$$
3. As $(a_1,b_1)=(0,\infty)$ $$p_1=1$$
4. 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...$$

Answer 2

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$.

Answer 3

I decided to post a second answer rather than edit my answer. If I have broken rules, please let me know, and I'll be happy to edit the original answer and delete this one. Please go easy on me, I'm new here. The work done here is related to my original post however I have made significant progress which I feel warrants a completely new post. I thought it is more transparent if I leave the original answer as is.

I've been playing with the problem and I have made some progress. I haven't really come up with a better solution than Xoff above, but would like to offer my approach. It's a little more brute force, maybe.

It has been established that $\lim_{n\rightarrow\infty}\mathbb{E}(X_n)$ is independent of $X_0$. I didn't initially understand why this is, but it does make intuitive sense after some thought. And after the analysis below, I realized that I didn't specify any initial state at all. I think it can start as any positive real number, actually without changing the limiting expectation. Therefore, I think the limit is most definitely an irrational number. I have another reason to believe that the limit is irrational, which I'll get to later.

The construction

Let the chain start in state $q_0\in\mathbb{Q}$. Define $\mathbb{Q}_0=\{q\}$, $\mathbb{Q}_1=\{1+q,\frac{1}{q}\}$, and recursively, $$\mathbb{Q}_{n+1}=\{\mathbb{Q}_n+1\}\cup\left\{\frac{1}{\mathbb{Q}_n}\right\}.$$ Note that this is not a disjoint union, in general.

Define $a^{(n)}_q$ on $q\in\mathbb{Q}_n$ to be the number of realizations of the process with $X_n=q$ conditioned on the fact that $X_0=q_0$ without regard to what happens after the first $n$ steps. $a^{(n)}_q=0$ if $q\notin\mathbb{Q}_n$. We have $a^{(0)}_{q_0}=1$, and $a^{(1)}_{1+q_0}=a^{(1)}_{1/q_0}=1$. Recursively $$ a^{(n+1)}_q=a^{(n)}_{q-1}+a^{(n)}_{1/q}. $$ And since there are $2^n$ total possible process realizations up to step $n$, $$ \sum_{q\in\mathbb{Q}_n}a^{(n)}_q=2^n. $$

It can also be shown that the number of elements in the $n^\text{th}$ set, $|\mathbb{Q}_n|$, is the $(n+3)^\text{th}$ Fibonacci number minus $1$ (with $f_1=f_2=1$). The first 13 terms for the sizes of the sets are $$\left\{|\mathbb{Q}_n|\right\}_{n\geq0}=1,2,4,7,12,20,33,54,88,143,232,376,609,\ldots.$$

Now take the expectation and its limit

Now we can write the expectation of $X_{n+2}$. Then we will work backwards to $X_n$ using the above equation. $$ \begin{aligned} \displaystyle \mathbb{E}(X_{n+2})&= \sum_{q\in\mathbb{Q}_{n+2}} q P(X_{n+2}=q)= \sum_{q\in\mathbb{Q}_{n+2}} q \frac{a^{(n+2)}_q}{2^{n+2}}.\\ &=\frac{1}{2}\sum_{q\in\mathbb{Q}_{n+2}} q \frac{a^{(n+1)}_{q-1}+a^{(n+1)}_{1/q}}{2^{n+1}}\\ &=\frac{1}{2}\sum_{q\in\mathbb{Q}_{n+2}} q \frac{a^{(n+1)}_{q-1}}{2^{n+1}}+\frac{1}{2}\sum_{q\in\mathbb{Q}_{n+2}}q\frac{a^{(n+1)}_{1/q}}{2^{n+1}}\\ &=\frac{1}{2} \sum_{\substack{q\in\mathbb{Q}_{n+2} \\ q-1\in\mathbb{Q}_{n+1}}} q \frac{a^{(n+1)}_{q-1}}{2^{n+1}}+ \frac{1}{2} \sum_{\substack{q\in\mathbb{Q}_{n+2} \\ 1/q\in\mathbb{Q}_{n+1}}}q\frac{a^{(n+1)}_{1/q}}{2^{n+1}}\\ &=\frac{1}{2} \sum_{ r\in\mathbb{Q}_{n+1}} (1+r) \frac{a^{(n+1)}_{r}}{2^{n+1}}+ \frac{1}{2} \sum_{ r\in\mathbb{Q}_{n+1}}\frac{1}{r}\frac{a^{(n+1)}_{r}}{2^{n+1}}\\ &=\frac{1}{2} \sum_{ r\in\mathbb{Q}_{n+1}} \frac{a^{(n+1)}_{r}}{2^{n+1}}+ \frac{1}{2} \sum_{ r\in\mathbb{Q}_{n+1}} r \frac{a^{(n+1)}_{r}}{2^{n+1}}+ \frac{1}{2} \sum_{ r\in\mathbb{Q}_{n+1}}\frac{1}{r}\frac{a^{(n+1)}_{r}}{2^{n+1}}\\ &=\frac{1}{2}+ \frac{1}{2}\mathbb{E}(X_{n+1})+ \frac{1}{2} \sum_{ r\in\mathbb{Q}_{n+1}}\frac{1}{r}\frac{a^{(n+1)}_{r}}{2^{n+1}}\\ &=\frac{1}{2}+ \frac{1}{2}\mathbb{E}(X_{n+1})+ \frac{1}{4} \sum_{ r\in\mathbb{Q}_{n+1}}\frac{1}{r}\frac{a^{(n)}_{r-1}+a^{(n)}_{1/r}}{2^{n}}\\ &=\frac{1}{2}+ \frac{1}{2}\mathbb{E}(X_{n+1})+ \frac{1}{4} \sum_{ r\in\mathbb{Q}_{n+1}}\frac{1}{r}\frac{a^{(n)}_{1/r}}{2^{n}}+ \frac{1}{4} \sum_{ r\in\mathbb{Q}_{n+1}}\frac{1}{r}\frac{a^{(n)}_{r-1}}{2^{n}}\\ &=\frac{1}{2}+ \frac{1}{2}\mathbb{E}(X_{n+1})+ \frac{1}{4} \sum_{ q\in\mathbb{Q}_{n}}q\frac{a^{(n)}_{q}}{2^{n}}+ \frac{1}{4} \sum_{ q\in\mathbb{Q}_{n}}\frac{1}{1+q}\frac{a^{(n)}_{q}}{2^{n}}\\ &=\frac{1}{2}+ \frac{1}{2}\mathbb{E}(X_{n+1})+ \frac{1}{4}\mathbb{E}(X_{n})+ \frac{1}{4}\mathbb{E}\left(\frac{1}{1+X_{n}}\right).\\ \end{aligned} $$ Now, we take the limit as $n\rightarrow\infty$ to get $$ \mathbb{E}(X)=\frac{1}{2}+ \frac{1}{2}\mathbb{E}(X)+ \frac{1}{4}\mathbb{E}(X)+ \frac{1}{4}\mathbb{E}\left(\frac{1}{1+X}\right). $$ Certainly $0\leq X \leq\infty$, thus $0\leq \mathbb{E} \left(1/(1+X)\right) \leq 1$. Solving we get $$ \begin{aligned} \mathbb{E}(X)&=2+\mathbb{E}\left(\frac{1}{1+X}\right)\\ &\leq 2+1 = 3. \end{aligned} $$ We actually get both upper and lower bounds: $2\leq \mathbb{E}(X) \leq 3$.

Refining the bounds

We can refine the estimate using the following technique. For the formula $\mathbb{E}(G(X))$: $$ \begin{aligned} &\text{ 1) Replace } X \text{ by both } 1+X \text{ and } 1/X\text{, } \quad\quad\quad\quad\quad\quad\quad\quad\\ &\text{ 2) Sum together and divide by } 2.\quad\quad\quad\quad\quad\quad\quad\quad \end{aligned}$$ This results in $$\mathbb{E}\left[G(X)\right]=\frac{1}{2}\left(\mathbb{E}\left[G(1+X)\right]+\mathbb{E}\left[G\left(\frac{1}{X}\right)\right]\right).$$ It takes some careful and tedious algebra to see that this holds, but it follows from the methods above.

Now we refine the bounds on $\mathbb{E}(1/(1+X))$. $$ \begin{aligned} \mathbb{E}\left(\frac{1}{1+X}\right) &=\frac{1}{2}\left[\mathbb{E}\left(\frac{1}{2+X}\right)+\mathbb{E}\left(\frac{1}{1+\frac{1}{X}}\right)\right]\\ &=\frac{1}{4} \left[\mathbb{E}\left(\frac{1}{3+X}\right)+\mathbb{E}\left(\frac{1}{2+\frac{1}{X}}\right) +\mathbb{E}\left(\frac{1}{1+\frac{1}{1+X}}\right)+\mathbb{E}\left(\frac{1}{1+X}\right)\right]\\ &=\frac{1}{8} \left[\mathbb{E}\left(\frac{1}{4+X}\right)+\mathbb{E}\left(\frac{1}{3+\frac{1}{X}}\right) +\mathbb{E}\left(\frac{1}{2+\frac{1}{1+X}}\right)+\mathbb{E}\left(\frac{1}{2+X}\right)\right.\\ &\quad\quad\quad\quad\left.+ \ \mathbb{E}\left(\frac{1}{1+\frac{1}{2+X}}\right)+\mathbb{E}\left(\frac{1}{1+\frac{1}{1+\frac{1}{X}}}\right) +\mathbb{E}\left(\frac{1}{2+X}\right)+\mathbb{E}\left(\frac{1}{1+\frac{1}{X}}\right)\right].\\ \end{aligned} $$ Using the last iteration of the equation above we can use the fact that when $Y=X$ or $1/X$ for $X\in[0,\infty]$ we can bound the finite continued fraction $$ 0\leq \frac{1}{a+Y}\leq \frac{1}{a}$$ $$ \frac{1}{a+\frac{1}{b}}\leq \frac{1}{a+\frac{1}{b+Y}}\leq \frac{1}{a}$$ to get $$\frac{1}{8}\left(0+0+\frac{1}{3}+0+\frac{2}{3}+\frac{1}{2}+0+0\right) \leq\mathbb{E}\left(\frac{1}{1+X}\right)\leq \frac{1}{8}\left(\frac{1}{4}+\frac{1}{3}+\frac{1}{2}+\frac{1}{2}+1+1+\frac{1}{2}+1\right).$$ Thus $$\frac{3}{16} \leq\mathbb{E}\left(\frac{1}{1+X}\right)\leq \frac{61}{96}.$$ Which yields $$2+\frac{3}{16} =2.1875\leq\mathbb{E}\left(X\right)\leq 2.63541\overline{6}= 2+\frac{61}{96}.$$ This process can be continued to refine the bounds even more and will result in longer and longer continued fractions. It's quite tedious, but works nicely and is a good counting exercise.

Is the limit rational or irrational?

I initially started to think the limit is irrational due to the presence of growing continued fractions. The power of two in the denominator grows larger and larger, and the length of some of the continued fractions continues to grow. In the limit, I think we will end up with every finite and infinite continued fraction $$\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cfrac{1}{a_4+\cdots}}}}$$ for all sequences of natural numbers $a_j\in\mathbb{N}$ for $j\in\mathbb{N}$. However, the probability of each continued fraction goes to zero as its length grows, and we will get a large number of multiples of each finite continued fraction. I'm not certain if any retain a positive probability, but doubt it.

The final nail might be that these results never used the fact that the initial state was a rational number. The limit should be independent of our starting value as long as it is a positive real number. Even if we start from an irrational number, the state space is still countable as it is generated from the operations 'add one' and 'divide into one'. Every element will be irrational, but the size of the state space grows like the Fibonacci numbers still. However, starting at $\phi-1\approx0.618$ delays the growth of the sizes of the sets. Sequences of irrationals can converge to rationals, so I am still not certain.

I have a feeling we can show that $\mathbb{E}(X_n)$ is a fraction with both a large numerator and larger denominator, and that the size of both goes to infinity with the difference between successive iterations getting smaller. That leads me to believe it does indeed converge to an irrational number as the size of the sequence of numbers which would repeat in the decimal expansion goes to infinity.

Answer 4

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.