1
$\begingroup$

Suppose you are only allowed to move along the edges of a square. At each vertex, you have an equal probability of picking any of the available routes (including doubling back on yourself). Is the probability greater that you arrive back where you started or at the diagonally opposite corner?

Well this is quite straightforward: you start walking and hit the first corner. There is a 1/2 chance of proceeding to the next corner and a 1/2 half chance of going back to the start. They are equally probable and the expected number of moves for both will be 2 (although I'm not sure why - what kind of distribution is this?)

OK. Now the harder case. Go to a cube. Each vertex you have 3 options. Is the probability higher for returning to starting point or ending up at diagonally opposite corner. I'm not really sure how to start this - should it be something to do with Markov chains?

Can we generalise it to an $n$-dimensional cube?

Thanks.

$\endgroup$
8
  • 1
    $\begingroup$ Indeed, in dimension $d=3$, the distance from the starting point is a random walk on $\{0,1,2,3\}$ which has transitions $1\to2$ with probability $2/3$, $1\to0$ with probability $1/3$, $2\to3$ with probability $1/3$ and $2\to1$ with probability $2/3$. You are after the probability to hit $0$ before $3$ starting from $1$, can you compute it? $\endgroup$
    – Did
    Feb 26, 2016 at 11:39
  • $\begingroup$ @Did Why are the probabilities 1/3 for $2 \rightarrow 3$ and 2/3 for $1 \rightarrow 2$? $\endgroup$
    – user11128
    Feb 26, 2016 at 12:00
  • $\begingroup$ Count the edges. $\endgroup$
    – Did
    Feb 26, 2016 at 12:02
  • $\begingroup$ I did this and agree with your probabilities. Now to calculate the total probability I don't fully understand the calculation done below. Do you have any hints? $\endgroup$
    – user11128
    Feb 26, 2016 at 15:04
  • $\begingroup$ Which "calculation done below"? $\endgroup$
    – Did
    Feb 26, 2016 at 16:27

1 Answer 1

1
$\begingroup$

end is the diagonally opposite vertex

p -> Probability to return at starting point before reaching at end from vertex at a distance 1

q -> Probability to return at starting point before reaching at end from vertex at a distance 2

A -> Probability to return at starting point before reaching at end from starting point

A = p and

p = 1/3 + 2/3 *q and

q = 2/3* p

So p = 1/3 +4/9p

5/9 p = 1/3

p = 3/5

$\endgroup$
2
  • $\begingroup$ Why does q=2/3*p? $\endgroup$
    – user11128
    Feb 26, 2016 at 14:22
  • $\begingroup$ from vertex at distance 2 you can reach at vertex at distance 1 with probability 2/3 . and with prob 1/3 you can reach at end $\endgroup$
    – Arpit Jain
    Feb 27, 2016 at 9:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .