A woman walks randomly on a nxn grid starting at the point (1,1) (the lower left corner). Each minute the women moves either to the right or up (so (a,b)-> (a+1,b) or (a,b)->(a,b+1). Her walk ends when she reaches the upper right corner, at the point (n,n). At each stage in which the woman walks she has a choice of 2 moves as she flips a fair coin in determine her next move.
If the woman is on the right edge ((i.e) (x,y) such that x=n) she automatically moves up and if she on the top edge she automatically moves right).
Define a probability space. What is the probability that the woman reaches the top row of the grid before reaching (n,n)?
I REALLY NEED HELP DEVELOPING THIS!
Going through a few examples, such as if she just zig zagged up then the probability would be (1/2)^(2n-1) because there are 2n steps, but subtract out the one right before she reaches (n,n), as her path is determined for her there and she won't have to flip the coin.
Help with logic, please?
Consider the sequence of moves, either up ($U$) or right ($R$). One such sequence is $UUUUURRRRR$, another is $URURURURUR$, etc. Because of the boundary conditions, there are always an equal number of $U$s and $R$s. If you reach the top row before reaching $(n, n)$, the last move will be $R$. What is the probability of this occurring?
Hint:
Further hint: