1

I am not a mathematician, just a user of mathematics, so perhaps this is the wrong place to ask, but there is a problem I need some help with.

You have a $n \times n$ grid, and you start at the $(1,1)$ square. You move randomly one square on the $x$ or $y$ axis (no diagonal movements allowed). You keep moving until you reach square $(n,n)$.

At that moment, the game ends. The variable of interest is $T$, the time it took you to reach the end position. It is clear to me that $T$ is always finite (just intuition: if you are not in $(n,n)$ you always have a chance to reach it, if you are there, you will never leave it, so if the game goes on for long enough you will end up there)

My question is about the distribution of $T$. I am interested in understanding how to define the distribution, and how to compute the expected value of $T$ as a function of $n$. Can you point me to something I could read about it?

Thanks in advance.

user2345448
  • 21
  • 1
  • Is the $n\times n$ grid from $(0,0)$ to $(n,n)$? – T.J. Gaffney Jan 13 '17 at 04:10
  • 1
    why will you never leave it once you're there? – spaceisdarkgreen Jan 13 '17 at 04:17
  • Does the player always go towards $(n, n)$ or they can go away too? – Gyanshu Jan 13 '17 at 04:17
  • @spaceisdarkgreen Because the game ends then. – Gyanshu Jan 13 '17 at 04:17
  • 1
    If they're on the right wall, is there a one in three chance that they'll move in each of the given directions? Or is left 50% while up and down are 25%? – T.J. Gaffney Jan 13 '17 at 04:19
  • @Gyanshu Oh, ok, don't really see how that adds to the intuition for why it's finite then. (agree that it's finite). Also if you always go toward it, then isn't it just a constant? – spaceisdarkgreen Jan 13 '17 at 04:19
  • @Gaffney Is the OP talking about the 'expected' time as in probability? – Gyanshu Jan 13 '17 at 04:20
  • @spaceisdarkgreen If we always go towards it, it is a constant but as value of $n$ changes, time also changes. So that makes it a function. – Gyanshu Jan 13 '17 at 04:22
  • Answer to comments:
    1. grid has $n$ columns and $n$ rows. so, it is (arbitrarily) numbered from $(1,1)$ to $(n,n)$. Any other numbering convention would be OK too
    2. you never leava $(n,n)$ because this is how the game is defined. it ends at the moment you reach that point.
    3. The player can move in any direction, towards the goal or away from it
    4. When the player hits a corner, it has only two possible moves. When the player hits a wall (top, bottom, left or right) in a place that it is not a corner, it has three possible moves. At any other place it has four possiblities.
     – user2345448 Jan 13 '17 at 11:46
  • If $T_n$ is the time it takes to end an $n\times n$ game, then it is a random variable. I am interested in its distribution, specially in its expected value.
    • – user2345448 Jan 13 '17 at 11:50