Wald's equation example controversy I'm trying to get a grip of Wald's equation, applying it to the following example.
Suppose, we have a simple sequence of fair coin flips, where heads wins us a dollar, while tails means loss of a dollar: $$\mathbb{P}(X_i=1)=\frac{1}{2}, \mathbb{P}(X_i=-1)=\frac{1}{2}$$
Suppose, that we're planning to gamble, tossing the coin until we win 3 dollars, that's our condition on stopping time N:
$$S_N = \sum_{i=1}^{N}X_N = 3$$
According to Wald's equation $$E(S_N) = E(X_i) \cdot E(N)$$
As we know, expectation of our fortune at stopping time is $E(S_N) = 3$, expectation of  a fair coin is zero: $E(X_i) = 0$, so I thought that Expectation of the stopping time $E(N)$ should grow to infinity. But seemingly it doesn't.
Our process is described by the following Markov chain:
$$
\begin{pmatrix}
\mathbb{P}(S_{i+1}=2) \\
\mathbb{P}(S_{i+1}=1) \\
\mathbb{P}(S_{i+1}=0) \\
\mathbb{P}(S_{i+1}=-1) \\
\mathbb{P}(S_{i+1}=-2) \\
\mathbb{P}(S_{i+1}=-3) \\
\dots
\end{pmatrix}
=
\begin{pmatrix}
0 & 0.5 & 0 & 0 & 0 & 0 & \dots\\
0.5 & 0 & 0.5 & 0 & 0 & 0 & \dots\\
0 & 0.5 & 0 & 0.5 & 0 & 0 & \dots\\
0 & 0 & 0.5 & 0 & 0.5 & 0 & \dots\\
0 & 0 & 0 & 0.5 & 0 & 0.5 & \dots\\
0 & 0 & 0 & 0 & 0.5 & 0 & \dots\\
0 & 0 & 0 & 0 & 0 & 0.5 & \dots\\
\dots & \dots & \dots & \dots & \dots & \dots & \dots
 \end{pmatrix} \cdot 
\begin{pmatrix}
\mathbb{P}(S_i=2) \\
\mathbb{P}(S_i=1) \\
\mathbb{P}(S_i=0) \\
\mathbb{P}(S_i=-1) \\
\mathbb{P}(S_i=-2) \\
\mathbb{P}(S_i=-3) \\
\dots
\end{pmatrix}
$$
Here each vector of $S_i(x)$ is infinite ($x \in (-\infty, 2]$, $x \in \mathbb{Z}$), but we can set a highly improbable lower bound (say, -20$) and the resulting 23x23 matrix will approximate our process well. We will calculate the Eigenvalues and Eigenvectors of that matrix to calculate the expected stopping time.
The probability of our fortune to be e.g. in state -1 dollar at step $i$ is approximated by $$\mathbb{P}(S_i = -1) = C \cdot \lambda^i \cdot V(-1)$$
where $\lambda$ is the main eigenvalue, $C$ is its quotient in eigenvalue decomposition and $V(-1)$ is the coordinate of main eigenvector, corresponding to $\mathbb{P}(S_i = -1)$.
The probability of stopping at the moment of time $i$ is $\mathbb{P}(S_{i}=3) = \mathbb{P}(S_{i-1}=2) \cdot 0.5$, thus expectation of stopping time
$$E(N) \approx (1 + 2 \cdot \lambda + 3 \cdot \lambda^2 + 4 \cdot \lambda^3 + \dots) \cdot C \cdot V(2) \cdot 0.5 = \frac{d(\lambda + \lambda^2 + \lambda^3 + \dots)}{d\lambda} \cdot C \cdot V(2) \cdot 0.5 = \frac{d(\frac{\lambda}{1-\lambda})}{d\lambda} \cdot C \cdot V(2) \cdot 0.5 = \frac{1}{(1-\lambda)^2} \cdot C \cdot V(2) \cdot 0.5 < \infty$$
So, $E(S_N) = E(X_i) \cdot E(N)$ means 3 = 0 * C, which is wrong. Can you see, what's wrong?
 A: Essentially your problem is the assumption that a large lower bound is "highly improbable".  In fact, no matter how low you set your lower bound, the random walk will almost surely (with probability $1$) hit either your lower bound or your upper bound, and the probability that it will hit the lower bound first does not go to zero very fast.  Suppose the distance between the bounds is some large $N$, and you start at a fixed distance $d$ from the upper bound.  The probability of hitting the lower bound first is
$$
P_{\text{low}}(d)=\frac{1}{2}P_{\text{low}}(d+1)+\frac{1}{2}P_{\text{low}}(d-1),
$$
with boundary conditions $P_{\text{low}}(0)=0$ and $P_{\text{low}}(N)=1$.  The solution is just $P_{\text{low}}(d)=d/N$; in particular, $P_{\text{low}}(N/2)=1/2$, which was already obvious by symmetry.  We can use this to prove that the expected stopping time is infinite.  Imagine starting at $x=0$.  The probability of reaching $x=N$ (the stopping position) before $x=-N$ is $1/2$, so the expected time to reach $x=N$ satisfies $S_{N} \ge N/2 + (N + S_{2N})/2=N+S_{2N}/2$ (given that we reached $x=\pm N$ first, we couldn't have done so in less than $N$ steps).  But this can be repeated: $S_{2N}/2\ge N + S_{4N}/4$, and $S_{4N}/4 \ge N + S_{8N}/8$, and so on.  Terminating after $k$ applications gives $S_{N}\ge k N$; since this holds for any $k$, we conclude that $S_{N}=\infty$.
A: $E(N)=\infty$ this is a very famous fact: symmetric random in 1d is null recurrent. For a proof of this fact, consult james norris's markov chain/suhov kelbert's prob and statistics by examples
The latter book might be available in russian.
This solving for eigenvalue thing is not correction infinite dimension. It is nice wishful thinking but unfortunately incorrect. You need to solve expected hitting time equations.
Let $S_i$ be expected hitting time of 3, starting at $i$.
You need the minimum non-negative solution to:
$S_i = 1 + S_{i-1}/2 + S_{i+1}/2$ for $i\leq 2$ with $S_3=0$ (*)
This is solved by $S_i=\infty$ for $i\leq 2$
Note you forgot to add the step each time you move!
