Why is a random walk a time-homogeneous Markov process?

Why is a random walk on $\mathbb{R}^d$ (see below) a time-homogeneous Markov process? Specifically, why does it satisfy requirement #2 of definition 17.3 that the map $\left(x,B\right)\mapsto\mathrm{P}_x\left[X\in B\right]$ be a stochastic kernel?

Relevant Definitions

Let $Y_1,Y_2,\dots$ be i.i.d.$\mathbb{R}^d$-valued random variables and let $$S_n^x=x+\sum_{i=1}^n Y_i\space\space \mathrm{for}\space x\in\mathbb{R}^d\space\mathrm{and}\space n\in\mathbb{N}_0$$

Define probability measures $\mathrm{P}_x$ on $\left(\left(\mathbb{R}^d\right)^{\mathbb{N}_0},\left(\mathcal{B}\left(\mathbb{R}^d\right)^{\otimes\mathbb{N}_0}\right)\right)$ by $\mathrm{P}_x=\mathrm{P}\circ\left(S^x\right)^{-1}$. Then the canonical process $X_n:\left(\mathbb{R}^d\right)^{\mathbb{N}_0}\rightarrow\mathbb{R}^d$ is a Markov chain with distributions $\left(\mathrm{P}_x\right)_{x\in\mathbb{R}^d}$. The process $X$ is called a random walk on $\mathbb{R}^d$ with initial value $x$. [Klenke, Example 17.5, p. 347]

-

You have to show that, for each $A$ fixed in the countable product $\sigma$-algebra, the map $x \to \mathbb{P}_x(A) = \mathbb{P}(S^x \in A)$ is measurable.

Since $S^x = S^0 + \underline{x}$, where $\underline{x} = (x, x, ..., x, x, ...)$, we have $\mathbb{P}_x(A) = \mathbb{P}_0(A - \underline{x})$. Setting $A_x = A - \underline{x}$, we have $\mathbb{P}_x(A) = \mathbb{P}_0(A_x) = \mathbb{E}_{\mathbb{P}_0}(\chi_{A_x})$.

Fact : If $(X, \mathcal{A})$ is a measurable space, $(\Omega,\mathcal{T}, \mathbb{P})$ is a probability space, and $f : X \times \Omega \to [0,+\infty]$ is a measurable map, then the map $x \to \mathbb{E}_{\mathbb{P}}(f(x, .))$ is measurable.

(if you want to prove it, it's an application of a Dynkin-class argument : prove it first for characteristic functions of measurable rectangles, and then extend the result in the usual way)

So, we are reduced to prove that the map $(x, \omega) \to \chi_{A_x}(\omega)$ is measurable. But this function is just the characteristic function of the set of all $(x, \omega)$ such that $\underline{x} + \omega \in A$, and since the map $(x, \omega) \to \underline{x} + \omega$ is measurable (exercise !), we are done.

-
Thanks, Ahriman! That's a terrific answer. I've got two suggestions, though. 1. It would be better to show that $\left(x,\omega\mapsto\underline{x}+\omega\right)$ before using the expression $\mathbb{P}_0\left(A-\underline{x}\right)$ in paragraph #2 rather than in the end, since this expression makes sense only if $A-\underline{x}$ is measurable. –  Evan Aad Aug 20 '12 at 13:07
2. Dynkin's class argument can be bypassed by invoking Fubini's theorem. See, for instance, part (a) of Ash & Doléans-Dade's statement of Fubini's Theorem (Theorem 2.6.4, p. 105) –  Evan Aad Aug 20 '12 at 13:08
Yes, you're right, but to prove this part of Fubini's theorem, you use exactly the same kind of Dynkin-class argument. –  Ahriman Aug 20 '12 at 13:19