Random Sequences with Respect to a Measure Defined by Two Linear Fractional Transformations

We define a probability measure on the Cantor space by using two linear fractional transformations consisting of computable real numbers. The measure can be a non-product measure on the Cantor space, on the other hand, it can also be the Bernoulli measure. We consider the constructive dimensions for the points which are random with respect to the measure. We examine limit frequencies of the outcome of 0 for such random points.

1. In [9], Lutz defined constructive dimension by using supergales instead of gales. Fenner [5] and Hitchcock [6] showed that gales can be used to define the dimension.

The author wishes to express his gratitude to the referees for helpful comments and suggesting references.

Authors and Affiliations

1. Graduate School of Mathematical Sciences, The University of Tokyo, 3-8-1, Komaba, Meguro, Tokyo, Japan

   Kazuki Okamura

Corresponding author

Correspondence to Kazuki Okamura.

This work was supported by Grant-in-Aid for JSPS fellows (24.8491).

Appendix

1.1 Computability of F(i, σ)

We will give a proof of that F(i, σ) defined in Section 2 is computable. Since −γ < −1 < α;, there exist \(\alpha ^{\prime } \in (-1, \alpha )\) and \(\beta ^{\prime } > \beta \) such that b _i x + d _i ≠0 for any \(x \in [\alpha ^{\prime }, \beta ^{\prime }]\), i = 0, 1. Then,

Lemma A.1

\(\alpha ^{\prime } < {\Phi }(^{t}\!A_{i}; \alpha ^{\prime }) \leq {\Phi }(^{t}\!A_{i}; \beta ^{\prime }) < \beta ^{\prime }, \, i = 0,1\).

Proof

By using the proof of Lemma 2.2 in [13], we have

Since d ₀>a ₀ > 0, Φ(^t A ₀;z)−z is strictly decreasing. By using \(\alpha ^{\prime } < \alpha \), \(\beta ^{\prime } > \beta \), and, α; ≤ Φ(^t A ₀;α;) ≤ Φ(^t A ₀;β) ≤ β, we have that \(\alpha ^{\prime } < {\Phi }(^{t}\!A_{0}; \alpha ^{\prime }) \leq {\Phi }(^{t}\! A_{0}; \beta ^{\prime }) < \beta ^{\prime }\). By using \(-\gamma < -1 < \alpha ^{\prime } < c_{1}/b_{1} < \beta ^{\prime }\), we have that \(\alpha ^{\prime } < {\Phi }(^{t}\! A_{1}; \alpha ^{\prime }) \leq {\Phi }(^{t}\! A_{1}; \beta ^{\prime }) < \beta ^{\prime }\). □

There exists \(L \in \mathbb {N}\) such that for any \(x, y \in [\alpha ^{\prime }, \beta ^{\prime }]\) and i∈{0, 1}, \(\left | {\Phi }(^{t}\!A_{i}; x) - {\Phi }(^{t}\!A_{i}; y) \right | \leq L|x-y|\). Since \(a_{0}, \dots , d_{1}\) are computable numbers, there exist computable functions \(F_{x} : \mathbb {N} \rightarrow \mathbb {Q}\) such that |F _x (n)−x|≤(L + 1)⁻ⁿ, \(x = a_{0}, \dots , d_{0}, a_{1}, \dots , d_{1}\).

Let \(\tilde {A}_{i, n} = \left (\begin {array}{cc}F_{a_{i}}(n) & F_{b_{i}}(n) \\F_{c_{i}}(n) & F_{d_{i}}(n) \end {array}\right )\), i = 0, 1, \(n \in \mathbb {N}\). Then,

Lemma A.2

There exists \(n \in \mathbb {N}\) such that for any n ≥ N and i = 0, 1,

• i  \({\Phi }(^{t}\!\tilde {A}_{i, n}; z) \text { is well-defined on } [\alpha ^{\prime }, \beta ^{\prime }]\).

• ii  \({\Phi }(^{t}\!\tilde A_{i, n}; z) \text { is increasing on } [\alpha ^{\prime }, \beta ^{\prime }]\).

• iii  \(\alpha ^{\prime } < {\Phi }(^{t}\!\tilde {A}_{i,n}; \alpha ^{\prime }) \leq {\Phi }(^{t}\!\tilde {A}_{i,n}; \beta ^{\prime }) < \beta ^{\prime }\).

• iv  \({\Phi }(^{t}\!\tilde A_{i,n}; z) \in [\alpha ^{\prime }, \beta ^{\prime }], \forall z \in [\alpha ^{\prime }, \beta ^{\prime }]\).

Proof

• (i)  By noting \(\lim _{n \rightarrow \infty } F_{b_{i}}(n) = b_{i}\), \(\lim _{n \rightarrow \infty } F_{d_{i}}(n) = d_{i}\), and, \(\inf _{x \in [\alpha ^{\prime }, \beta ^{\prime }], i = 0,1} |b_{i}x + d_{i}| > 0\), we have that \(\inf _{x \in [\alpha ^{\prime }, \beta ^{\prime }], i = 0,1} |F_{b_{i}}(n)x + F_{d_{i}}(n)| > 0\) for any sufficiently large n.

• (ii)  By using \(\det A_{i} > 0\) and \(\lim _{n \rightarrow \infty } F_{x}(n) = x\), \(x = a_{0}, \dots , d_{1}\), we have that \(\det \tilde A_{i, n} > 0\) for any sufficiently large n.

• (iii)  This follows from \(\lim _{n \rightarrow \infty } {\Phi }(^{t}\!\tilde A_{i,n}; \alpha ^{\prime }) = {\Phi }(^{t}\! A_{i}; \alpha ^{\prime })\), \(\lim _{n \rightarrow \infty } {\Phi }(^{t}\!\tilde A_{i,n}; \beta ^{\prime }) = {\Phi }(^{t}\! A_{i}; \beta ^{\prime })\), i = 0, 1, and Lemma A.1.

• (iv)  This follows from (ii) and (iii).

□

Let \(D := \{(i, \sigma ) \in \mathbb {N} \times \{0,1\}^{\ast } : i \leq |\sigma | \}\). We define a function \(\tilde {F} : D \times \mathbb {N} \rightarrow \mathbb {Q}\) by \(\tilde {F} (0, \sigma , n) := 0\), and, \(\tilde {F} (i, \sigma , n) := {\Phi } (^{t}\!\tilde {A}_{\sigma (i-1), n+N} ; \tilde {F} (i-1, \sigma , n)), \, 1 \leq i \leq |\sigma |\). Due to Lemma A.2, this is well-defined and \(\tilde {F}(i, \sigma , n) \in [\alpha ^{\prime }, \beta ^{\prime }]\). This is a computable function.

We let \(G(m) := \max _{x \in [\alpha ^{\prime }, \beta ^{\prime }], j = 0,1} |{\Phi }(^{t}\!A_{j}; x) - {\Phi }(^{t}\!\tilde {A}_{j, m+N}; x) |\), H(0, n):=0, and, \(H(i, m) := \max _{\sigma : |\sigma | \geq i} |F(i, \sigma ) - \tilde {F} (i, \sigma , m)|, \, i \geq 1, \, m \in \mathbb {N}\). Then,

Hence, H(i, m) ≤ (L + 1)ⁱ G(m). By noting that \(|F_{x}(n) - x| \leq (L+1)^{-m}, x = a_{0}, \dots , d_{1}\), we see that there exists a constant C > 0 and \(M \in \mathbb {N}\) such that G(m) ≤ C(L + 1)^−m for any m ≥ M. Therefore, there exists a computable function \(g : \mathbb {N} \rightarrow \mathbb {N}\) such that g(0) ≥ N, and, G(g(m)) ≤ m ⁻¹, m ≥ 1.

Let f(i, n) := g((L + 2)ⁱ2ⁿ) and define \(u : D \times \mathbb {N} \rightarrow \mathbb {Q}\) by u(0, σ, n):=0, \(u(i, \sigma , n) := \tilde {F}(i, \sigma , f(i, n))\), \(n \in \mathbb {N}, 1 \leq i \leq |\sigma |\). Then, u is a computable function and |F(i, σ)−u(i, σ, n)|≤H(i, f(i, n)) ≤ (L + 1)ⁱ G(f(i, n)) ≤ 2⁻ⁿ.

Thus we see that \(f : D \rightarrow \mathbb {R}\) is a computable function.

Reprints and permissions