Keywords: Characteristic Function, Fourier Transformation
Consider a one-dimensional straight line. Someone stays at point $0$ at time $t = 0$. He will randomly go left ($-1$) or go right ($+1$) with the same probability. The length of each step at the nth step will be $\lambda^n$. What is the distribution at the $n$th step?
1. The domain of the distribution
Recall the fundamental theorems in the real analysis:
1.1 The cardinality of the N and $2^N$ (Cantor’s Theorem)
Let $N$ denote the set of natural number, and the $2^N$ denote the power set of the natural number. The Cantor’s Theorem is one of the most tricky one I learned in real analysis. It is simple but tricky for sure. Cantor claimed that $N$ and $2^N$ cannot have equal cardinality.
Suppose for the sake of contradiction that the sets $N$ and $2^X$ had equal cardinality. Then there exist a bijection $f: N \xrightarrow{} 2^N$ between $N$ and the power set of $N$. Now consider the set:
$A = \{x \in N: x \notin f(x)\}$. Note that since A is a subset of $N$, then it is an element of the power set. Since f is a bijection, there must exist $x \in X$ such that $f(x) = A$. (The set is well-defined.)
Let $x$ denote $f^{-1}(A)$. If $x \in A$, then $x \notin f(x) = A$, which is a contradiction. If $x \notin A$, then $x \in f(x) = A$, which is a contradiction again. Therefore, this is not such bijection.
Proposition: $2^N$ has the same cardinality of $\mathbb{R}$. (读者自证不难)
1.2 Conclusion
We can conclude that the domain is uncountable (In the $n$th step, the number of the reachable points is $2^n$).
2. The solution of the equation generated by the ‘first step analysis’
Let $P_n(x)$ denote the probability mass function at the $n$th step at the point n. I believe almost everyone will follow the first step analysis like at the first glance. However, a convolutional form will be much more easily to solve the problem. (That’s why the name of this series will be named as Trickster.)
$P_n(x) = \int_{\mathbb{R}} P_{n - 1}(x - x^\prime)f_{n}(x^\prime) dx^\prime$
where $f_n(x^\prime) = \frac{1}{2} [\delta_{-\lambda^n}(x) + \delta_{\lambda^n}(x)]$
Comment: 一般来说，我们考虑Markov Chain的时候会从状态出发，甚至我们的转移概率都是使用从状态A到状态B定义的。这种做法是符合直觉并具有一般性的。但是有时如果将状态与距离相联系，将会产生卷积的形式，此时在傅里叶变化中会更加容易处理。
Let $F_n(w)$ denote the Fourier transformation of $P_n(x)$, $G_n(w)$ denote the Fourier transformation of $f_n(x)$.
$G_n(v) = \int_{-\infty}^{\infty} \frac{1}{2} [\delta_{-\lambda^n}(x) + \delta_{\lambda^n}(x)] e^{ivx} dx = \frac{1}{2}[cos(v \lambda^n) + cos(-v \lambda^n)] = cos(v\lambda^n)$
$F_n(v) = F_{n-1}(v)G_n(v) = F_0(v)\Pi_{n = 1}^NG(v) = \Pi_{n = 1}^N cos(v\lambda^n)$
(Note that $F_0(v) = \int_{\mathbb{R}} \delta_0(x) e^{ivx}dx = 1$)
Therefore, the probability mass function at the $N$th step can be written as:
$P_n(x) = \frac{1}{2\pi}\int_{\mathbb{R}} \Pi_{n = 1}^N cos(v\lambda^n) e^{-ivx}dv$
Example: $\lambda = \frac{1}{2}$:
$\Pi_{n = 1}^N \cos(\frac{v}{2^n}) = \Pi_{n = 1}^N \frac{\sin(v/2^{n-1})}{2\sin(v/2^n)} = \frac{\sin(v)}{2^N \sin(v/2^N)}$
According to L’Hopital’s Law, $2^N \sin(v/2^N) \xrightarrow{N = \infty} v$
Therefore, $\lim\limits_{N \xrightarrow{} \infty} P_N(x) = \frac{1}{2\pi}\int_{\mathbb{R}} \frac{\sin(v)}{v}e^{-ivx}dv$
, which is the uniform distribution.
Comments