Since we have an infinite sample space, we should calculate f(p) by a limiting process. Let f[n](p) be the probability that a binary tree of depth n has a green path. If we attach a single edge to the root node, the probability of a green path becomes p f[n](p). Attach two of these to a new root node, and we have a binary tree of depth n+1, and the probability of a green path is f[n+1](p) = 1 - (1 - p f[n](p))^2 = f[n](p) (2 p - p^2 f[n](p)). Assuming thatthe limit of f[n](p) exists, let us define f(p) as that limit. Then f(p) satisfies f(p) = f(p) (2 p - p^2 f(p)). The two fixed points are f(p) = 0 and f(p) = (2 p - 1)/p^2. Let F(x) = x (2 p - p^2 x), F'(x) = 2 p - 2 p^2 x. The fixed point x is stable under iteration when |F'(x)| < 1. Since F'(0) = 2 p, the fixed point 0 is stable when p < 1/2. Since F'((2 p - 1)/p^2) = 2 - 2 p, this fixed point is stable when p > 1/2. Finally, when p = 1/2, the iteration x <-- F(x) = x (1 - x/4) is strictly decreasing and bounded below by 0, and so must have a limit, and the only possible limit is the fixed point 0. -- Gene
________________________________ From: Michael Kleber <michael.kleber@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Sunday, March 4, 2012 2:48 PM Subject: Re: [math-fun] math-fun Digest, Vol 109, Issue 3
I think the easier relation is
f(p) = p * (2 f(p) - f(p)^2)
That is, a tree with an infinite path from root is a tree whose root is green, and at least one of whose children has an infinite path from root. There is an f(p)^2, yes, but no quadratic equation needed.
--Michael
On Sun, Mar 4, 2012 at 5:00 PM, Warren Smith <warren.wds@gmail.com> wrote:
From: Dan Asimov <dasimov@earthlink.net> I saw this problem in some stuff I was reading: Consider the standard binary tree with infinitely many levels. Suppose each edge is colored green with probability = p. What is the probability f(p) that there exists an infinite green path starting at the root?
--Let q=1-p and g(p)=1-f(p). Then g(p) obeys
g(p) = q^2 + p*q*2*g(p) + p^2 * g(p)^2
you may now solve the quadratic equation to deduce g(p) and hence f(p). Don't choose the wrong root.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun