Let's consider two Random Walks, $$x^{(1)}_t = x_0 + \sum_{i=1}^{t}\xi^{(1)}_i,$$ $$x^{(2)}_t = x_0 + \sum_{i=1}^{t}\xi^{(2)}_i.$$ The random variables $\xi^{(1)}_i$ are i. i. d. They take values on a set $K \subset \mathbb{Z}$ which is not necessarily finite. Their probability distributions are respectively $P^{(1)}$ and $P^{(2)}$. Assume that these distributions are such that $\forall k \in \mathbb{Z}$, $P^{(1)}(\{ \xi^{(1)}_i \geq k \}) \geq P^{(2)}( \{ \xi^{(2)}_i \geq k \} )$.
Now $\forall m \in \mathbb{Z}$ define the event, $$\{ \forall t \in \mathbb{N}, \, \, \, x_t \geq x_0 - m \},$$ i.e. the walk will never cross a certain barrier placed in $x_0 - m$. How can I prove formally that the probability of this event for the random walk (1) is larger or equal to the probability of the same event for random walk (2)?
The expectations $E_{P^{(1)}}[\xi^{(1)}]$ and $E_{P^{(2)}}[\xi^{(2)}]$are both larger than $0$.
Edit: The induction proof failed. See the addendum for a proof of $(1)$ from a different direction.
An approach via mathematical induction. First of all, note that:
$$\{\forall t \in \Bbb N: x_t \ge x_0-m\} = \bigcap_{t \in \Bbb N} \{\forall s \le t: x_s \ge x_0-m\}$$
Let $S^m$ be the set on the LHS, and $S^m_t$ those on the RHS. By the fact that $P^{(1)}$ and $P^{(2)}$ are probability measures, we have:
$$P^{(i)}(S^m) = \lim_{t \to \infty} P^{(i)}(S^m_t)$$
Since limits preserve inequalities, it will suffice to show the inequality holds for all $S^m_t$; this makes our life a lot easier because we can deal with one time-step at once, reducing the number of events and the complexity of them.
We can now show by induction on $t$ that:
$$\forall m \in \Bbb N: P^{(1)}(S^m_t) \le P^{(2)}(S^m_t) \tag{1}$$
which leads us to the desired conclusion. Can you take it from this outline?
Addendum: As requested, a more explicit outline. Sadly, my purported sketch proof didn't work out as I made some irreparable errors. Thus we will have to turn to a direct approach using sums (for the moment; I'm sure there are elegant arguments as well).
Despite the fact that $P^{(i)}$ are not the formally correct symbols, they naturally induce the measures playing a role so I will stick with this abuse of notation. Observe that:
$$P^{(i)}(S^m_2) = \sum_{k_1 \ge -m} \,\sum_{k_2 \ge -k_1-m} P^{(i)}(\xi^{(i)}_1 = k_1)P^{(i)}(\xi^{(i)}_2 = k_2)$$
and in general, denoting $\sigma_\ell = \sum_{j=1}^{\ell-1} k_j$:
$$\begin{align}P^{(i)}(S^m_t) &= \sum_{k_1 \ge -m} \cdots \sum_{k_t \ge -\sigma_t-m} \ \prod_{j=1}^t P^{(i)}(\xi^{(i)}_j = k_j)\end{align}$$
where the summation subscripts contain $k_\ell \ge \sigma_\ell - m$ for $1 \le \ell \le t$.
By investigating the collection of $t$-tuples included in our summation, we can always exchange the summations to have the last one range over $k_i$ (of course, taking care to describe our collection of $t$-tuples accordingly). Let us restrict to the case $t=2$ to make the idea clear; general $t$ would only obscure the heart of the argument (besides being verbose and error-prone to formulate):
$$\begin{align} P^{(2)}(S^m_2) &= \sum_{k_1 \ge -m} \,\sum_{k_2 \ge -k_1-m} P^{(2)}(\xi^{(2)}_1 = k_1)P^{(2)}(\xi^{(2)}_2 = k_2) \\ &= \sum_{k_1 \ge -m} \, P^{(2)}(\xi^{(2)}_1 = k_1)P^{(2)}(\xi^{(2)}_2 \ge -m -k_1)\\ & \le \sum_{k_1 \ge -m} \, P^{(2)}(\xi^{(2)}_1 = k_1)P^{(1)}(\xi^{(1)}_2 \ge -m -k_1) & & \text{by assumption} \\ & = \sum_{k_2 = -\infty}^\infty \, \sum_{\substack{k_1 \ge k_2-m \\ k_1 \ge-m}} P^{(2)}(\xi^{(2)}_1 = k_1)P^{(1)}(\xi^{(1)}_2 = k_2) & & \text{rearranging of indices} \\ & = \sum_{k_2 = -\infty}^\infty \, P^{(2)}(\xi^{(2)}_1 \ge \min\{k_2-m,-m\})P^{(1)}(\xi^{(1)}_2 = k_2) \\ & \le \sum_{k_2 = -\infty}^\infty \, P^{(1)}(\xi^{(1)}_1 \ge \min\{k_2-m,-m\})P^{(1)}(\xi^{(1)}_2 = k_2) \\ & = P^{(1)}(S^m_2) \end{align}$$
The careless exchanging of summations is justified because all of them converge absolutely. For general $t$, the idea is the same, only the amount of characters necessary to describe the summation limits increases.
Hopefully there will be other answers because this is very inelegant. (My original approach tripped over some unaccounted conditional probabilities, which I later observed to violate desired inequalities in some cases. Thus I had to start again from scratch.)