Probabilistic Steps (Random Walk) Again!

The man must either take one more step up than down or one more step down that up over the course of the $11$ steps. So if we look at triplets of the form $(S,U,D)$ for the number of steps staying put, going up or going down, respectively, the possibilities are

$(10,1,0), (10,0,1), (8,2,1), (8,1,2), (6,3,2), (6,2,3),$

$(4,4,3), (4,3,4), (2,5,4), (2,4,5), (0,5,6), (0,6,5)$ .

We then need to consider all the permutations for each of these triplets and factor in the probabilities for each movement, (or lack of such). This gives us a probability of

$\displaystyle\sum_{k=0}^{5} \dfrac{11!}{(10 - 2k)!*k!*(k+1)!} * (0.1)^{10 - 2k} * ((0.4)^{k+1}(0.5)^{k} + (0.4)^{k}(0.5)^{k+1}) = \boxed{0.241}$

to $3$ decimal places.

Solved in Python using Monte Carlo sampling:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

from random import random
go = {'u':1,'d':-1,'s':0}
def goal(steps):
    position = 0
    for step in steps:
        position += go[step]
    return abs(position) == 1
yes = 0.0
trials = 10000000
for a in xrange(trials):
    steps = ''
    for b in xrange(11):
        roll = random()
        if roll < .1:
            new = 's'
        elif roll < .5:
            new = 'd'
        else:
            new = 'u'
        steps = steps + new
    if goal(steps):
        yes += 1
print "Answer:", yes/trials

This gave me a decent approximation at 0.2411825 .

1 step away: 0.241331211990001

2 steps away: 0.182990566549980

0 step away: 0.107931142010016

and etc.

Convert (0.4 U + 0.5 D + 0.1 S)^11 into two for calculations required:

(0.4 + 0.5 + 0.1)^11 consists of 3^11 i.e. 177147 branching, while

(U + D + S)^11 be assigned into (2 + 1/ 2 + 1)^11 or (1/ 2 + 2 + 1)^11 or (3 + 1/ 3 + 1)^11 and etc for identification of combination of steps,

Turn on the logic required for combination of some number of 2, 1/ 2 and 1 for example for a product of 11 elements chosen for 1/ 2 or 2 to indicate 1 move, summing up all obtained 0.241331211990001. During the process of calculation using Excel, the sums are checked to be 1 for every column to ensure correctness.

Answer required is 0.241331211990001

Note: Paste of copied cells can be eased with technique of column of cells with wanted side length with content of cells arbitrary or not being aware. Forget about binomial coefficients or nCr for this question and multiply series by series fundamentally.

Let's indicate the event 'being one step up the initial position after 11 steps' as $U$ , and 'being one step down the initial position after 11 steps' as $D$ . The probability of being one step away from the original position is

$\displaystyle \mathbb{P}(U \cup D)=\mathbb{P}(U)+\mathbb{P}(D)$ .

Being one step up at the end of the process means that one more step-up has been done respect to the total steps-down. So the possible triplets are

$\begin{bmatrix} \text{Up} & \text{Down} & \text{Stop} \\ 6 & 5 & 0 \\ 5 & 4 & 2 \\ 4 & 3 & 4 \\ 3 & 2 & 6 \\ 2 & 1 & 8 \\ 1 & 0 & 10 \end{bmatrix}$

Considering that a single step up, down and a stop has, respectively $\mathbb{P}(u)=\frac{2}{4}$ , $\mathbb{P}(d)=\frac{1}{2}$ , $\mathbb{P}(s)=\frac{1}{10}$ , we can write

$\displaystyle \mathbb{P}(U)=\bigg(\frac{2}{4}\bigg)^6 \bigg(\frac{1}{2}\bigg)^5 \bigg(\frac{1}{10}\bigg)^0 \binom{11}{6} \binom{5}{5}+...+\bigg(\frac{2}{4}\bigg)^1 \bigg(\frac{1}{2}\bigg)^0 \bigg(\frac{1}{10}\bigg)^{10} \binom{11}{1} \binom{10}{0}=\sum_{i=1}^{6} \bigg(\frac{2}{4}\bigg)^i \bigg(\frac{1}{2}\bigg)^{i-1} \bigg(\frac{1}{10}\bigg)^{12-2i} \binom{11}{i} \binom{11-i}{i-1}$

as well for the probability of being one step down at the 11th step, we can reason in the same way just switching the Up/Down columns

$\displaystyle \mathbb{P}(D)=\sum_{i=1}^{6} \bigg(\frac{1}{2}\bigg)^i \bigg(\frac{2}{4}\bigg)^{i-1} \bigg(\frac{1}{10}\bigg)^{12-2i} \binom{11}{i} \binom{11-i}{i-1}$

Eventually

$\displaystyle \mathbb{P}(U \cup D)=\mathbb{P}(U)+\mathbb{P}(D)=\boxed{0.24133}$