Wikipedia:Reference desk/Archives/Mathematics/2014 July 19

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 19

Random walk on polygon

What is the easiest way to show that, for a symmetrical random walk starting on a vertex of a polygon, the expected value of the number of steps to visit all n vertices is n(n-1)/2? And how would one derive the expected value of the number of steps to cover all n edges? →86.146.61.61 (talk) 12:30, 19 July 2014 (UTC)

For the second part, it will take as long to reach all vertices of the polygon as to reach n (necessarily consecutive) integers in a random walk on the integers, and it will take as long to traverse all edges as to reach n+1 integers, so if n(n-1)/2 is the right answer to the first part then n(n+1)/2 is the right answer to the second. -- BenRG (talk) 03:01, 20 July 2014 (UTC)

I don't know about the easiest way, but here is a way. Suppose you know that it takes on average n(n-1)/2 steps to visit every vertex for n vertices. Now suppose you're on an n+1-gon. The number of steps needed to visit all n+1 vertices = (the number of steps needed to visit n vertices) + (the number of steps needed to reach the n+1st vertex having just reached the nth vertex). Look at a random walk, basically as sequence of lefts and rights, where you have just visited the nth vertex on the last step. Perform that same walk on an n-gon and you also get a walk where you have visited the nth vertex on the last step. Also, any walk on an n-gon where you where you visit the nth vertex on the last step will, if performed on an n+1-gon, will give a walk that visits exactly n vertices and reaches the nth vertex on the last step. This is using the fact that the walk can't make a complete circuit without having first reached all n vertices. So the number of walks on an n-gon where you reach n vertices after exactly S steps is the same as the number of walks on an n+1-gon where you reach the n vertices after exactly S steps. In other words, the (the number of steps needed to visit n vertices) part of the sum given above is the same for an n+1-gos as it is for an n-gon, and we already know that number is on average n(n-1)/2. So if the second number is, on average, n, then the sum is n(n-1)/2 + n = (n+1)n/2 then we have proved the formula for n+1 and the result follows by induction. Therefor it is sufficient to show that the second term in the sum is n, that is, from a position where a walk has visited n vertices and visited the nth vertex on the last step, it takes on average n steps to get to the n+1st vertex.

So lets start in a position where n of the vertices have been visited, and the nth vertex was visited on the last step. The n vertices visited must be contiguous and the last vertex must be at one end, since if the walk ended in the middle it must have previously reached both ends. Therefor the vertices that have been visited form a path, with our current position at one of the ends, and we want to know how long on average will it take to fall off that path if the walk is continued. Falling off the path is equivalent to reaching the n+1st vertex since going off the path at either end will result in reaching the n+1st vertex. Number the vertices visited so far from 1 to n, then going off the path would be the same as reaching 0 or n+1.

Now we have the following restatement of the problem, given a random walk starting at 1 or n, show that the expected number of steps required to reach either 0 or n+1 is n. To do this it's probably easier, to actually do more than is required. Namely, given a random walk starting at any number k between 1 and n, find the expected number E(k) of steps before the walk reaches either 0 or n+1. Take E(0)=E(n+1)=0. From k after 1 step you land on k-1 with probability 1/2 and k+1 with probability 1/2. So E(k) = 1 + (E(k-1)+E(k+1))/2. This gives you a system of n equations in n unknown, namely

2E(1)-E(2) = 2

-E(1)+2E(2)-E(3) = 2

-E(2)+2E(3)-E(4) = 2

...

2E(n-1)-E(n) = 2

The coefficient matrix for the system is nonsingular, in fact it's easy to show by induction that its determinant is n+1. So there is a unique solution to the system. Since we suspect that E(1)=n, start with that value and plug in the equations to the the remaining ones, which come out as E(2)=2(n-1), E(3)=3(n-2), ... and in general E(k)=k(n-k+1). It's not hard to verify that these values satisfy the equations and since a solution is unique these must be the values of the E(k). Plug in k=1 and k=n to get E(0)=E(n)=n as desired. I've glossed over a point here in that I'm assuming without proof that E(k) is finite. This isn't extremely hard to show, though it's a bit messy, and this response is already overly long. So I'll leave it as an exercise.

Random walks are well studied and so are Markov processes which are a generalization, so I assume most of the above can be simplified a great deal by using results from those theories, but I'm giving a completely naive proof that does not rely on such specialized knowledge. According to my calculations, if instead of just moving to adjacent vertices you can go to any vertex with equal probability, the result is the same. So there may be a larger class of graphs for which the expected time to visit all vertices is n(n-1)/2. Also, it might be interesting to what happens if the probabilities going left and right are not the same. It seems clear that as the probability of going left approaches 1 then the expected number of steps will approach n-1. --RDBury (talk) 06:00, 20 July 2014 (UTC)

Thanks, that's probably as easy as it gets. I came across a paper which was really beyond me, and the n(n-1)/2 result for an n-gon with equal left/right probability just appeared in a load of confusing detail, with extra notation being defined from time to time along the way. It does seem strange if the result isn't in some sense standard (I deduced it by considering a triangle and quadrilateral from first principles, having been unable to find it by direct searching), likewise n being the expected number of steps to escape from one end of an n-path.

Yes, covering edges is equivalent to covering one more vertex.→86.146.61.61 (talk) 16:18, 20 July 2014 (UTC)

Is it a metric space?

I am not a mathematician but I need this for a project I am involved with. Given a final set of complex numbers; if each complex number defines one dimension of a topological space is this space a metric space? In short can a distance be defined on it? I feel it can be but want to make sure. I think this follows from "Metrics on vector spaces" in the article "Metric" here. Thanks, --AboutFace 22 (talk) 22:48, 19 July 2014 (UTC)

You'll have to be more specific about how exactly you construct your space. Any set can be given a metric- the discrete metric can always be used no matter what the set is. Probably you're wondering if some "nicer" metric exists, but it's not clear from your question exactly what you're talking about. Do you mean the vectorspace defined by taking your finite set of numbers as a basis? Staecker (talk) 23:02, 19 July 2014 (UTC)

Thank you for the answer. Honestly I am surprised my question is unclear. I will need a day or two to think about what you've said. --AboutFace 22 (talk) 01:27, 20 July 2014 (UTC)

L² norm states:

On an n-dimensional complex space Cⁿ the most common norm is

$\|{\boldsymbol {z}}\|:={\sqrt {|z_{1}|^{2}+\cdots +|z_{n}|^{2}}}={\sqrt {z_{1}{\bar {z}}_{1}+\cdots +z_{n}{\bar {z}}_{n}}}.$

Are you asking if this yields a metric space? -- ToE 08:45, 22 July 2014 (UTC)

ToE, thank you very much. Yes, I want to make sure that if I have a set of complex numbers and a norm defined as you stated the set will be a metric space. It is hard for me even to express it the way you did in such a way that it will look as a mathematical notation. Many thanks, --AboutFace 22 (talk) 02:13, 24 July 2014 (UTC)

I actually read the Euclidean norm you referred to a number of times as well as some related topology but could not make the final step, to declare it a metric space. --AboutFace 22 (talk) 02:17, 24 July 2014 (UTC)

Then yes. See Normed vector space#Topological structure. -- ToE 21:14, 24 July 2014 (UTC)

Thank you much.It is an important thing for me. --AboutFace 22 (talk) 00:21, 25 July 2014 (UTC)

Perhaps you will be even happier to know that it is a complete metric space. -- ToE 22:00, 25 July 2014 (UTC)