How Do You Calculate Probabilities of Random Events Occuring in Sequence?

Question

So I have a series:

$f(x_{n+1})=x_n \pm t$

and

$f(x_0)=W$

What I'd like to calculate is the probability in terms of $t$ and $W$ (assuming they're any constant $W>t$) that any $f(x_q)=0$ for all $q$ from $[0,n]$ assuming that $t$ is either randomly added or subtracted with $50/50$ probability in each iteration.

Specifically, I'd like to know not just the equation, but how you get to it.

I feel like it should be

$P=\frac{t}{2^nW}$

but it's more just an intuition in that I know the probability should go down if $\frac{W}{t}$ goes up because you'd need more trades, but it falls apart in the example where $W=100$ and $t=1$ and $P\neq 0$ for $n=1$

Thanks in advance for any pointers.

Answer 1

You can transform it by dividing by $t$, so $f(x_{n+1})=f(x)\pm 1$ and $f(x_0)=\frac Wt=w$ Clearly if $w$ is not an integer, you will never have $f(x)=0$ Even more, if $w$ is odd, you must take an odd number of steps, while if $w$ is even, you must take an even number of steps. If you want $f(x_n)=0$, you must have $w$ more negative steps than positive ones, so must have $\frac 12(w+n)$ negative ones and $\frac 12(n-w)$ positive ones. Now look up the binomial distribution to find the chance you get $\frac 12(w+n)$ heads out of $n$ coin tosses.

Answer 2

UPDATE:

The correct equation appears to be:

$$ P = 1- \prod\limits_{n=1}^{q} {\left(1-\dbinom{n}{\frac{W+tn}{2t}}\frac{(n+1)\bmod 2}{2^n}\right)} $$

Everything below was inaccurate because I forgot you can't add probabilities without eventually going over one.

This was all wrong:
It appears the equation I was looking for is a modified form of the binomial distribution such that

$$ P = \sum\limits_{n=1}^{q} {\left\{ \begin{array}{rl} \dbinom{n}{\frac{\frac{W}{t}+n}{2}}\frac{1}{2^n} &\mbox{ if $n$ is even} \\ 0 &\mbox{ if $n$ is odd} \end{array} \right.} $$

Which can be simplified to $$ P = \sum\limits_{n=1}^{q} {\left\{ \begin{array}{rl} \dbinom{n}{\frac{W+tn}{2t}}\frac{1}{2^n} &\mbox{ if $n$ is even} \\ 0 &\mbox{ if $n$ is odd} \end{array} \right.} $$

This gives me zero for all $n$ such that $n<\frac{W}{t}$ because for all $n\frac{W}{t}$ I'd be trying to choose more elements than the set contains in the combination operation, and if we are randomly adding or subtracting $t$, an odd number of iterations such that $n> \frac{W}{t}$ we cannot reach zero because there must be more additions of $t$ than subtractions (or vice versa) in excess of the intial $\frac{W}{t}$.

Further, I can bring it to the form: $$ P = \sum\limits_{n=1}^{\lfloor {\frac{q}{2}} \rfloor} {\dbinom{2n-1}{\frac{W+2tn-t}{2t}}\frac{1}{2^{2n-1}}} $$

to eliminate the even/odd branching. I think.

Thanks to Ross Millikan for pointing me in the right direction.

The only problem I have left is that the components become incomputably large and small respectively rather quickly ($q \approx 1035$ in Excel or Desmos) despite the probability growing with $q$.

Note: I'm posting this for peer review, not because I'm sure it's right.