Definition
Assume G is some graph and is some path of length n on G. In other words, are vertices of G such that and are neighbors. Then the loop erasure of is a new simple path created by erasing all the loops of in chronological order. Formally, we define indices inductively using
where "max" here means up to the length of the path . The induction stops when for some we have . Assume this happens at J i.e. is the last . Then the loop erasure of, denoted by is a simple path of length J defined by
Now let G be some graph, let v be a vertex of G, and let R be a random walk on G starting from v. Let T be some stopping time for R. Then the loop-erased random walk until time T is LE(R). In other words, take R from its beginning until T — that's a (random) path — erase all the loops in chronological order as above — you get a random simple path.
The stopping time T may be fixed, i.e. one may perform n steps and then loop-erase. However, it is usually more natural to take T to be the hitting time in some set. For example, let G be the graph Z2 and let R be a random walk starting from the point (0,0). Let T be the time when R first hits the circle of radius 100 (we mean here of course a discretized circle). LE(R) is called the loop-erased random walk starting at (0,0) and stopped at the circle.
Read more about this topic: Loop-erased Random Walk
Famous quotes containing the word definition:
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)
“Mothers often are too easily intimidated by their children’s negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.”
—Elaine Heffner (20th century)
“According to our social pyramid, all men who feel displaced racially, culturally, and/or because of economic hardships will turn on those whom they feel they can order and humiliate, usually women, children, and animals—just as they have been ordered and humiliated by those privileged few who are in power. However, this definition does not explain why there are privileged men who behave this way toward women.”
—Ana Castillo (b. 1953)