How to prove the independent and stationary increment of a poisson process? Given a Poisson distribution with parameter $\lambda$ (basically a Poisson process), how can I prove that this Poisson process is independent and stationary increment? Or the memoryless property: $$P(N(t+s)|N(t))=P(N(s))$$ From what I learned, the basic definition of a Poission process includes self increment and then from that you can get the 'Poisson distribution' form of the process. I am just wondering how the reverse proof goes? 
 A: This is modified from my answer to a related question. The only thing this answer assumes you already know about the Poisson process is that $\mathbb{P}(N_t=n)$ is a Poisson-distributed random variable (for a proof, see page 4 here). It uses the construction of the Poisson process using exponential inter-arrival times.
It turns out that this construction has independent increments (as I show below) and other properties, and that these properties actually uniquely characterize the process. I do not prove or address or use this unique characterization of the process at all in my answer below.
Proof of independent increments (following Durrett's Probability Theory and Examples, pp. 155-156, 4th edition)   $\newcommand{\Prob}{\mathbb{P}}$
$N_t = \max \{ n \ge 0: T_n \le t  \}$ where $T_0 = 0$ and $T_n = S_1+ \dots S_n$, $S_n \sim \exp(\lambda)$ i.i.d. RV's.
Let $T_1' = T_{N_s +1} - s$ be the amount of time that elapses after time $s$ until the next arrival. The following computation shows that $T_1'$ is independent of $N_s$: $$\Prob(T_1' \ge t|N_s = n) = \Prob(T_{N_s+1}  \ge (s+t) | N_s = n) \\ = \Prob(T_{n+1} \ge (s+t), T_n \le s  )/ \Prob(N_s = n)\,.$$ The numerator equals: $$ \Prob(T_{n+1} \ge (s+t), T_n \le s ) = \int_0^s f_{T_n}(u) \Prob(S_{n+1} \ge (s+t) - u)du \\= \int_0^s \frac{\lambda^n u^{n-1}}{(n-1)!}e^{-\lambda u} e^{-\lambda( (s+t) -u)}du = e^{-\lambda (s+t)}\frac{\lambda t^n}{n!}. $$ Using the fact that $\mathbb{P}(N_t=n)$ is Poisson-distributed, the denominator is $$\Prob(N_t=n) = e^{-\lambda s}(\lambda s)^n/n!\,,$$ so: $$\Prob(T_{n+1} \ge (s+t)| N_s = n) = \frac{e^{- \lambda(s+t)}}{e^{-\lambda s}} = e^{-\lambda t} =\Prob(T_1' \ge t)  \,. $$
For $k \ge 2$, define $T_k' = T_{N_t +k} - T_{N_t +k-1}$, the amount of time elapsing between the $(k-1)$th arrival after time $s$ and the $k$th arrival after time $s$. Observing that: $$\Prob(T_n \le s, T_{n+1} \ge u, T_{n+k} - T_{n+k-1} \ge v_k, k=2,\dots,K) = \Prob(T_{n} \le s, T_{n+1} \ge u) \prod_{k=2}^{K} \Prob(S_{n+k} \ge v_k) \,, $$ it follows that the $T_1', T_2', \dots$ are i.i.d. and independent of $N_t$. In other words, arrivals after time $s$ are independent of $N_s$ and have the same distribution as the original sequence.
From this follows the desired conclusion of independent increments, namely that if $0:= s_0 < s_1 < \dots < s_m$ then $N_{s_i} - N_{s_i - 1}$, $i = 1, \dots, n$ are independent.
This is because the vector $( N_{s_2} - N_{s_1}, \dots, N_{s_m} - N_{s_m -1}  )$ is measurable with respect to $\sigma(T_k', k \ge 1)$ and thus independent of $N_{s_1}$. Then it follows by induction: $$\Prob(N_{s_i} - N_{s_{i- 1}} = k_1, i = 1, \dots, n) = \prod_{i=1}^m \exp (-\lambda (s_i - s_{i-1})) \frac{\lambda  (s_i - s_{i-1} )^{k_i}}{k_i!}\\ = \prod_{i=1}^{m} \Prob(N_{s_i} - N_{s_{i-1}} = k_i) \,. \square $$
The fact that $T_1'$ is independent of $N_s$ amounts essentially to the memoryless property of the exponential distribution. Note: I imagine this is similar to the argument that you used to show that $N_{s+t}-N_s$ is independent of $N_s$. The only difference here is that now we are renewing the process at a random time, as opposed to a deterministic time.
