Alice and Bob dance Tango, every second they choose randomly if to step forward or to step two steps backwards. The dance is finished when Alice and Bob tackle a wall that is $m$ steps behind the starting point ($m$ is positive)
I need to find the upper bound of the probability that the dance lasts atleast 3m seconds.
So first I start with Binom distribution approach, $X~B(n,1/2)$.
Where n is the number of steps they went, and 1/2 is which way should they step (forward or backwards).
Then I calculate the distance, if X is the number of steps forward, then $2(n-x)$ are the steps backwards.
Then, the distance will be $X - 2(n-x)$ which should be equal to $-m$, because the dance stops after m steps. In conclusion, $3x - 3n = -m$
Now, I need to use Chernov Upper bound formula because we're using Binom.
Also we can conculude that $E[x] = n*p$, thus $E[x] = 0.5n$
The question is How do I build the the $Pr[ ? ? ? ]$ for atleast $3m$ seconds.
If the question was for given n, and after n seconds, and assuming alice and bob went more steps forward than backward(distance greater than zero) I'd build it this way:
$Pr[3x-3n \ge 1] = Pr [ X \ge n/2 + 1 + n/6 ]$ which is $\le$ than value of Chernov's formula (doesn't really matter) for upper bounds.
Maybe I'm missing some basic understanding about that distribution, maybe $X$ should be Binomically distributed like that: $X~B(m,1/2)$. and make it like that: $Pr[3x-3m \ge 3m] \le value$.