4
$\begingroup$

Can you prove a random walk might never hit 0, given a probability system that only uses the finite additivity axiom (rather than the standard countable additivity axiom)?

Specifically: Imagine the standard random walk problem on the nonnegative integers: We start at integer location $i>0$. Every step we independently move left with probability $\theta$, and right with probability $1-\theta$. Assume $0<\theta < 1/2$. Let $q$ be the probability that we ever hit 0, given we start at location 1. By the repeated structure of the problem, we can infer: $$ q=\theta + q^2(1-\theta) $$ The difficulty is that this quadratic has two roots: $q=1$ and $q=\frac{\theta}{1-\theta}$. If we can prove that $q<1$, then we infer $q=\frac{\theta}{1-\theta}$.

The answer is $q=\theta/(1-\theta)$ under the standard probability axioms, which includes the countable additivity axiom. Is this provable with only finite additivity, i.e., $P[\cup_{i=1}^k A_i] = \sum_{i=1}^k P[A_i]$ for finite integers $k$ and for disjoint events $A_i$? Or is it undecidable?


Note: The union bound $P[\cup_{i=1}^{\infty} A_i] \leq \sum_{i=1}^{\infty} P[A_i]$ is unprovable without countable additivity.

$\endgroup$
  • 1
    $\begingroup$ Perhaps this paper will be helpful. $\endgroup$ – grndl Jan 15 '17 at 18:51
  • $\begingroup$ @aduh : Thanks! That title seems exactly what I was talking about. Unfortunately I cannot download it due to license restrictions. I will try again in a few days, perhaps I can download it from campus. But I am curious now: If you have access to the paper, I wonder if you can tell me if they use Banach limits to construct an example system for which the probability is 1? (You can use Banach limits to show existence of finitely-but-not-countably-additive probability systems, so I expect it to also be useful for the random walk question). $\endgroup$ – Michael Jan 16 '17 at 7:06
1
$\begingroup$

This is a long comment:

How would you define the finitely additive probability law of the random walk?

With a standard probability model, the random walk could, for instance, be defined in a probability space $(\Omega,\mathscr{F},\mathbb{P})$, where $\Omega:=\{-1,1\}^{\mathbb{N}}$ with $x\in\Omega$ specifying the sequence of moves, $\mathscr{F}$ is the product $\sigma$-algebra and $\mathbb{P}$ is the joint probability law of the random moves (a product measure). The intuitive concept of a random walk only prescribes the finite-dimensional marginals of $\mathbb{P}$ (i.e., the measure of the cylinder sets) and one would rely on Carathéodory's extension theorem (or something similar) to be sure that the probability of every event in $\mathscr{F}$ is determined uniquely and consistently.

If you discard the countable additivity axiom, then it is not clear that the probability of the event $E:=\{\text{the RW eventually hits the origin}\}$ is uniquely determined by the finite-dimensional marginals. We know there is at least one model (the countably additive one) in which $\mathbb{P}(E)=q$, but there might be other non-countably additive models in which $\mathbb{P}(E)$ has a different value.

$\endgroup$
  • $\begingroup$ Yes, I was thinking of the probability law along the lines of your paragraph (perhaps using the same sigma algebra of events and the same finite-dimensional description of the infinite process of iid moves as the standard model). This law extends to some events in the sigma algebra, but it is not clear to me which ones, or if the event $E$ in question is included. Actually, I’m not even sure if the equation $q = \theta + q^2 (1-\theta)$ can be rigorously justified without countable additivity. $\endgroup$ – Michael Jan 8 '17 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.