I need to calculate the amount of steps the person needs to take to have a probability of 50% to be aleast 10m away from his starting point (in both directions). He has a probability of 50% of moving in either direction.
Could someone tell if I'm thinking the right way or set me in the good direction. That would be very helpfull.
Thanks in advance!
Answer to first posed question which was later edited
The target will be reached in an odd number of steps.
Let $S_{m}$ denote the number of steps that separate the drunkard from the target after taking $1+2m$ steps.
Then $S_{0}=2$ and $S_{1}\in\left\{ 0,2\right\} $ so a walk that ends with $S_{m}=0$ will have shape: $$\left(S_{0},S_{1},\dots,S_{m-1},S_{m}\right)=\left(2,2,\dots,2,0\right)$$
After taking exactly one step we are in status $S_{0}=2$ and there are $3$ possible outcomes for the next two steps:
It is a loop of $2$ steps that hits the original starting point. This has probability $\frac{1}{2}$ to occur.
It is a loop of $2$ steps that does not hit the original starting position. This has probability $\frac{1}{4}$ to occur.
It is an arrival at the target. This has probability $\frac{1}{4}$ to occur.
So - taking the first two bullets together - when the first step is taken and the next $2$ steps are taken then there is probability $\frac{3}{4}$ on making a loop and probability $\frac{1}{4}$ on reaching the target.
That means that the probability that the target is reached in exactly $1+2m$ steps equals: $$\frac{1}{4}\left(\frac{3}{4}\right)^{m-1}$$ for $m=1,2,\dots$.
Then the probability of reaching the target in at most $1+2m$ steps is: $$\sum_{k=1}^{m}\frac{1}{4}\left(\frac{3}{4}\right)^{k-1}=1-\left(\frac{3}{4}\right)^{m}$$
To be found is the smallest $m$ that satisfies $1-\left(\frac{3}{4}\right)^{m}\geq0.95$ which is $m_0:=11$
So the final answer is: $$n_0=1+2m_0=23$$
edit (answer to edited question)
For $n=0,1,2,\dots$ let $X_{n}$ denote the distance of the drunkard from his starting point.
Then to be found are expressions for $P\left(X_{n}=i\right)$ for $i=0,1,2,3$.
After finding them we can go for finding the smallest $n$ that satisfies:
$$1-P\left(X_{n}=0\right)-P\left(X_{n}=1\right)-P\left(X_{n}=2\right)-P\left(X_{n}=3\right)\geq0.95$$ or equivalently: $$P\left(X_{n}=0\right)+P\left(X_{n}=1\right)+P\left(X_{n}=2\right)+P\left(X_{n}=3\right)\leq0.05$$
Under the convention that $\binom{n}{k}=0$ if $k\notin\left\{ 0,1,2,\dots,n\right\} $ we find for nonnegative integer $n$:
$P\left(X_{n}=0\right)=2^{-n}\binom{n}{\frac{1}{2}n}$
$P\left(X_{n}=1\right)=2^{-n}\left[\binom{n}{\frac{1}{2}n-\frac{1}{2}}+\binom{n}{\frac{1}{2}n+\frac{1}{2}}\right]$
$P\left(X_{n}=2\right)=2^{-n}\left[\binom{n}{\frac{1}{2}n-1}+\binom{n}{\frac{1}{2}n+1}\right]$
$P\left(X_{n}=3\right)=2^{-n}\left[\binom{n}{\frac{1}{2}n-\frac{3}{2}}+\binom{n}{\frac{1}{2}n+\frac{3}{2}}\right]$
I leave the rest to you.
Let $X_t = \text{How far away the drunkard is from the origin after } t \text{ steps}$; $X_t$ is a random variable.
We're interested in $t$, as $$\Bbb{P}(|X_t| \ge 3 ) = 0.95$$ Which is the probability of the drunkard being at least $3$ meters away from the origin, after $t$ steps. (Which we know is $95\%$.)
So we need to find the distribution of $X_t$ for $t \in \{1,2,3,\dots\}$.
Since $X_t$ is gotten through $t$ steps that are exactly alike, it makes sense to introduce another notation:
$$X_t = M_1 + M_2 + M_3, + \dots + M_t$$
where $\forall i \in \{1,2,\dots,t\} \ \ M_i $ are random (left or right) movements, a.k.a. random variables with distribution
$$M_i = \begin{cases}+1 \text{ with probablity } \frac{1}{2} \\[2ex] -1 \text{ with probablity } \frac{1}{2}\end{cases}$$
So $M_i \sim 2\ \text{Bernoulli}\left(\frac{1}{2}\right)-1$
Note: Regular $\text{Bernoulli}\left(\frac{1}{2}\right)$ is $\begin{cases}1 \text{ with probablity } \frac{1}{2} \\ 0 \text{ with probablity } \frac{1}{2}\end{cases}$, so multiplying it with $2$ and subtracting $1$ transforms it into the type of variable we're looking for.
We can find a pattern and prove it by induction:
$$\begin{align}M_1 + M_2 &= \begin{cases}2 \text{ with probability } \frac{1}{4} \\[2ex] 0 \text{ with probability } \frac{1}{2} = \frac{2}{4} \\[2ex] -2 \text{ with probability } \frac{1}{4}\end{cases} \\[2ex] M_1 + M_2 + M_3 &= \begin{cases}3 \text{ with probability } \frac{1}{8} \\[2ex] 1 \text{ with probability } \frac{1}{2}\cdot\frac{1}{4} + \frac{1}{2}\cdot\frac{1}{4} = \frac{3}{8} \\[2ex] -1 \text{ with probability } \frac{3}{8} \\[2ex] -3 \text{ with probability } \frac{1}{8}\end{cases} \\[2ex] M_1 + M_2 + M_3 + M_4 &= \begin{cases}4 \text{ with probability } \frac{1}{16} \\[2ex] 2 \text{ with probability } \frac{1}{2}\cdot\frac{3}{8}+\frac{1}{2}\cdot\frac{1}{8} = \frac{4}{16} \\[2ex] 0 \text{ with probability } \frac{1}{2}\cdot\frac{3}{8}+\frac{1}{2}\cdot\frac{3}{8} = \frac{6}{16} \\[2ex] -2 \text{ with probability } \frac{4}{16} \\[2ex] -4 \text{ with probability } \frac{1}{16} \end{cases} \\[2ex] &\quad \vdots \\[2ex] \sum_{i=1}^t M_i &= t-2j \text{ with probability } \frac{\binom{t}{j}}{2^t} \quad \forall j \in \{0,1,\dots,t\}\\[2ex] \end{align}$$ Or $$\Bbb{P}(X_t = t-2j) = \Bbb{P}\left(\sum_{i=1}^t M_i = t-2j\right) = \frac{\binom{t}{j}}{2^t}, \quad \forall j \in \{0,1,\dots,t\}$$ Which isn't very suprising, since the sum of $\text{Bernoulli}$ variables has $\text{Binomial}$ distribution. We just had to slightly modify the $\text{Binomial}$ distribution, since we had $2 \text{Bernoulli} -1 $ instead of $\text{Bernoulli}$.
The proof is very simple, it works for $t=1$:
$$M_1 = \begin{cases}1 \text{ with probablity } \frac{\binom{1}{1}}{2^1} = \frac{1}{2} \\[2ex] 1-2 = -1 \text{ with probablity } \frac{\binom{1}{0}}{2^1} = \frac{1}{2}\end{cases}$$
Let's assume it works up until $t-1$ and prove for $t$:
$$\begin{align}&\Bbb{P}(M_1 + \dots + M_t = t-2j) = \\ = &\frac{1}{2}\Bbb{P}(M_1+\dots+M_{t-1} = (t-1)-2(j-1)) + \frac{1}{2}\Bbb{P}(M_1+\dots+M_{t-1} = (t-1)-2j) = \\ = &\frac{1}{2} \left(\frac{\binom{t-1}{j-1}+\binom{t-1}{j}}{2^{t-1}}\right) \stackrel{\text{Pascal-triangle rule}}{=} \frac{\binom{t}{j}}{2^t}\end{align}$$
So
$$\begin{align}\Bbb{P}(|X_t| \ge 3) &= 0.95 \\ \sum_{i=3}^\infty \Bbb{P}(X_t=i) + \sum_{i=3}^\infty \Bbb{P}(X_t=-i) &= 0.95 \\ \Bbb{P}(X_t=2) + \Bbb{P}(X_t=1) + \Bbb{P}(X_t=0) + \Bbb{P}(X_t=-1)+ \Bbb{P}(X_t=-2) &= 0.05 \\[1ex] 2\Bbb{P}(X_t=2) + 2\Bbb{P}(X_t=1) + \Bbb{P}(X_t=0) &= 0.05 \\ \end{align}$$
Since $j$ has to be in $j \in \{0,1,\dots,t\}$, and $t$ has to be odd (since as we saw earlier, you can only get to an odd value in odd number of steps), this eliminates a couple options:
$$0 = t-2j \rightarrow j = \frac{t}{2} \rightarrow j \notin \{0,1,\dots,t\}$$ $$1 = t-2j \rightarrow j = \frac{t-1}{2} \rightarrow j \in \{0,1,\dots,t\}$$ $$2 = t-2j \rightarrow j = \frac{t-2}{2} \rightarrow j \notin \{0,1,\dots,t\}$$
This simplifies the above equation to
$$\begin{align} 2\Bbb{P}(X_t=1) &= 0.05 \\ \frac{\binom{t}{\frac{t-1}{2}}}{2^t} &= 0.025 \\ \end{align}$$ We can solve this in Wolfram Alpha, but we unfortunately get no $t > 0$ solution, which means the probability of the drunkard travelling at least $3$ meters can never go above $95\%$.
This is easy to see, since for the equivalent equation
$$\begin{align} \binom{t}{\frac{t-1}{2}} &= 2^t \cdot 0.025 \\ \end{align}$$
The left side is approximately
$$\begin{align} \binom{t}{\frac{t-1}{2}} &\approx \binom{t}{\frac{t}{2}} = \frac{t!}{\left(\frac{t}{2}\right)!^2}\\ \end{align}$$
Which has a lower bound for $t \ge 0$
$$\begin{align} \frac{t!}{\left(\frac{t}{2}\right)!^2} \ge 1 \end{align}$$
And then grows more rapidly than $2^t \cdot 0.025$.
However, with different inputs, like $5$ meters instead of $3$, or a different probability than $0.95$, we can likely find a solution, since the above approximation won't be accurate - meaning the left and right sides can actually meet.
