You have a triangle ABC with an ant that starts at vertex 'A.' The ant can move in either direction (either to vertex 'B' or to vertex 'C') with equal probability (50% chance). What is the probability the ant approaches vertex 'C' from 'A' and not from 'B'?In a similar situation, you have a square ABCD (labeled clockwise with 'A' in the top, left corner) and an ant at 'A.' At each vertex, the ant can move to an adjacent vertex with probability 1/2. What is the probability the ant will approach 'D' from 'A' and not 'C'?If you had an n-gon of the same construction, could you generalize the result? Can you prove it?

gambler's ruin in disguise.could easily generalize to asymmetric prob. going clockwise & counterclockwise. maybe some polyhedrons to make it more interesting?

matlab code. split the last vertex into 2, stochastic matrixN=3; % 3 is for triangle, it actually creates 4 vertices, another termination pointstoc=diag(.5*ones(1,N),-1)+... diag(.5*ones(1,N),1);stoc(:,1)=[1;zeros(N,1)];stoc(:,end)=[zeros(N,1);1];startvertex=[0;1;zeros(N-1,1)];final_distribution= stoc^1000*startvertexyou can also get the expression of the actual eigenvectors with E.V = 1 in the initial state.

QuoteOriginally posted by: wileyswgambler's ruin in disguise.could easily generalize to asymmetric prob. going clockwise & counterclockwise. maybe some polyhedrons to make it more interesting?Yes break open the triangle at point C so it becomes a line segment (someone asked in a another thread).Asymmetric prob. is still called gambler's ruin. ----- ----- -----Polyhedrons:The analogous question for a tetrahedron would be:(Q1) Label the vertices of a tetrahedron A, B, C, D. The ant starts at A and at each vertex chooses one of the 3 edges to move along with equal probability. What is the probability that the ant approaches D for the first time from A, and not from either B or C?This is straightforward.----- ----- -----Q1 can be viewed as a simple case of a "gambler's ruin" in the plane (which has probably been considered somewhere):Consider the "random walk" on the truncated hexagonal tiling. At each node there is an equal probability of going to one of the three adjacent nodes.(Q2) Let A be a vertex in the truncated hexagonal tiling. Then there are unique vertices B and C connected to A and each other, so that the triangle ABC is a subset of the tiling. Given an integer n, let B_n be the set of vertices of the tiling whose graph distance from ABC is n. For each vertex X of B_n, let f_n(A,X) be the probability that the random walk on the tiling starting at A reaches X before any other vertex of B_n. Find an expression for f_n(A,X).Q1 is a special case of Q2 with n=1 and X the element of B_1 closest to A.----- ----- -----Generalize the OP and Q1 to arbitrary number of dimensions.(Q3) Consider an n-dimensional simplex (n=3 is the tetrahedron). Pick two adjacent vertices A and B. An ant begins at vertex A, and at each vertex X it randomly picks one of the n edges coincident on X to travel along. What is the probability that the first time it arrives at B is directly from vertex A?

repoman, since you dug this out, here is what i had in mind about the polyhedron case.dont quite remember where i first learned about this: there is an interesting connection between random walk problems and resistance networks. one solution for your Q3 is to link each pair of vertices with a 1-ohm resistor, then apply some voltage between point A and B. the fraction of the current going through the resistor on side AB with respect to the total current going outside B is the answer.say B is grounded and voltage at A is V, then the rest vertices all have same voltage of V/2 by symmetry of the simplex, i.e., no current going through the side between any pair of vertices not including A and B. so it's simply 1 ohm and (n-1) resistors of 2 ohm in parallel (note in n-dimension, total of n+1 vertices). the current proportion is thus 1:(n-1)/2, or the prob of 2/(n+1)

QuoteOriginally posted by: wileyswrepoman, since you dug this out, here is what i had in mind about the polyhedron case.dont quite remember where i first learned about this: there is an interesting connection between random walk problems and resistance networks. one solution for your Q3 is to link each pair of vertices with a 1-ohm resistor, then apply some voltage between point A and B. the fraction of the current going through the resistor on side AB with respect to the total current going outside B is the answer.say B is grounded and voltage at A is V, then the rest vertices all have same voltage of V/2 by symmetry of the simplex, i.e., no current going through the side between any pair of vertices not including A and B. so it's simply 1 ohm and (n-1) resistors of 2 ohm in parallel (note in n-dimension, total of n+1 vertices). the current proportion is thus 1 : (n-1)/2, or the prob of 2/(n+1)That's very interesting. I had noticed the connection between such circuits and 2-dimensional random walks ... apparently it wasn't an original thought If you find some reference please post it.For now, I will solve Q3 (which includes Q1) using standard results on Markov chains:We have two nodes A and B on an n-dimensional simplex. (Recall that the simplex generalizes a triangle to n-dimensions: There are n+1 vertices, and every pair of vertices has an edge between them. Hence n+1 choose 2 edges.)We want the probability that a random ant starting from A arrives at B for the first time traveling along the edge from A to B. This corresponds to the Markov chain obtained by "breaking open" the simplex at the point B and making each of the terminal nodes an absorbing state.Therefore, the Markov chain is described by the transition graph which is an (n-1)-simplex S with each of its n vertices also attached to a single absorbing node, where each node v in S has 0 probability of staying at v and an equal probability, 1/n, of moving to any one of the n attached nodes. The idea is simple, and the picture of the case n=3 is below, with the absorption nodes in red and the other nodes (i.e. S) in green. The absorption nodes B, B' and B'' correspond to the ant arriving at B the first time directly from A, C and D, respectively:Back to the general case, the Markov chain has 2n states which we enumerate (for notational convenience) as 1,...,n,n+1,...,2n, where the last n states are absorbing and thus 1,...,n are transient (eventually the Markov chain does not return to a transient state).The enumeration is also made so that transition probabilities p(i,j) are, for all i=1,...,np(i,j)=0 if j=ip(i,j)=1/n if j != i and j=1,...,np(i,j)=1/n if j=i+np(i,j)=0 otherwise.In other words, state i+n is the absorption node attached to node i. We also assume that the Markov chains begins in state 1 (ant at node A).Our chain is absorbing, meaning it has at least one absorption state and every state communicates with some absorption state. For a finite Markov chain, this is equivalent to every state being either transient or absorbing. We can apply the following basic result.Theorem. Suppose an absorbing time-homogeneous Markov chain has states {1,...,n}, and that i is an absorbing state. Let x_j be the probability of reaching state i starting from state j. Then the x_j's are the unique solution to the linear system of equations(1) x_i = 1.(2) x_j = 0 for every absorbing state j != i.(3) x_k = x_1 p(k,1) + x_2 p(k,2) + ... + x_n p(k,n) for every transient state k. Applying the theorem to our Markov chain, state n+1 corresponds to the ant arriving at node B from A, and we get(1) x_(n+1) = 1.(2) x_j = 0 for all j=n+2,...,2n.(3a) x_1 = 1/n * (x_2 + x_3 + ... + x_n + 1),(3b) x_i = 1/n * (x_1 + ... + x_(i-1) + x_(i+1) + ... + x_n) for all i=2,3,...,n.Using the fact that by symmetry, x_2=x_3=...=x_n, this is easily sovled as:x_1 = 2 / (n+1)x_i = 1 / (n+1) for all i=2,...,n.For an ant on a triangle (i.e. n=2 dimensional simplex), the probability of arriving at B traveling from A is 2 / 3. For an ant on a tetrahedron the probability is 1/2. For an ant on an n-simplex the answer is 2/(n+1). Looking at this again, it is not hard to get the system of linear equations without the Markov chain theorem. Considering the simple form of the answer, maybe there is an even easier method or some general result?