Application of the central limit theorem on Markov chains

105 Views Asked by At

I'm studying a paper from Rosenfeld about bitcoin mining pools. He formulates a Markov chain by the definition:

\begin{equation*} \begin{aligned} X_{t+1} - X_t= \begin{cases} B - (1 - f) \cdot B \cdot p, & \text{w/ prob } p \\ - (1 - f) \cdot B & \text{w/ prob } (1 - p). \end{cases} \end{aligned} \end{equation*}

Then he goes on computing the expectation of the difference, which equals $fpB$, and the variance which is approximately $pB^2$. If you plug it in, that's relatively easy to confirm. So far, so good. Now he goes on arguing that by the central limit theorem, the long-term behavior of the stochastic process above is equivalent to that of \begin{equation*} \begin{aligned} X_{t+1} - X_t= \begin{cases} + \sqrt{p} B, & \text{w/ prob }\ \frac{1+f\sqrt{p} }{2} \\ - \sqrt{p} B, & \text{w/ prob } \frac{1-f\sqrt{p} }{2} . \end{cases} \end{aligned} \end{equation*} which has the same variance and expectation.

Now I know the central limit theorem, but I'm not seeing how it is applied to reformulate the first difference definition to the second. Help would be appreciated! Best wishes.

Rosenfeld, Meni. (2011). Analysis of Bitcoin Pooled Mining Reward Systems. arXiv preprint arXiv. 1112. File is available under https://arxiv.org/pdf/1112.4980.pdf. I'm referring to the derivation made on page 37 of said paper.

1

There are 1 best solutions below

2
On BEST ANSWER

Let $D_{t+1} = X_{t+1} - X_t$ and $\bar{D}_T = \frac{1}{T} \sum_{t=1}^T D_t$. Let $E[D_1] = \mu$ and $\text{Var}(D_1) = \sigma^2$. Since the $D_t$ are i.i.d., the central limit theorem implies $\sqrt{T} \frac{\bar{D}_T - \mu}{\sigma}$ converges in distribution to $N(0,1)$. Since $T \bar{D}_T = X_T - X_0$, this result says something about how the Markov chain $(X_t)$ behaves for large $T$.

If for some reason you have another Markov chain $X'_t$ (and define $D'_t$ and $\bar{D}'_T$ analogously) such that $D_t$ and $D'_t$ have the same mean and variance, then the CLT again implies $\sqrt{T}\frac{\bar{D}'_T - \mu}{\sigma}$ converges in distribution to $N(0,1)$. So this other Markov chain $X'_t$ has a similar distribution for large $t$ as the original Markov chain $X_t$.