It turns out all the prof wanted was the average number of steps
required to get to an instance of all heads, which is 1/p = (3/2)^n.
I was making the problem harder than it needed to be, apparently. The
poly term had to do with checking the solution.
The larger story is sort of interesting and has to do with solving the
3-coloring problem which is in general NP-Complete (it can be reduced
to a 3-sat boolean formula.
But there is an odd situation: if you restrict each of the vertices to
have a forbidden color, then you can reduce the problem to a 2-sat
formula, solvable in P. So the trick is to randomly scatter a
restriction over the vertices, checking with the poly 2-sat each time
to see if your random distribution of restrictions worked. The
probability of success for each vertex is 2/3 .. i.e. if you restrict
a vertex to 2 colors, there's a 2/3 chance one of them is in the
assumed 3-coloring.
So getting them all correct vastly improves the computational time,
from a 3^n exhaustive search to a (3/2)^n search for the restricted
case, with a poly 2-sat test to see if you got a good set of
restrictions.
-- Owen
On May 5, 2010, at 8:56 AM, Owen Densmore wrote:
OK, no good deed goes unpunished! This approach works quite well,
and indeed, the second expression, at least 1, gives great results.
Now the second part of the question: Show that we get at least 1
with "high probability" by choosing t to be (3/2)^n * poly(n) ..
where n is the original n in n-flips of the highly biased (2/3
heads) coin.
If n is 10, for example, using (3/2)^n I get 0.632175881706547, but
if I include a polynomial factor of n I get 0.999958413014979 ..
interesting! I'd call that "high probability"!
So what I lack here is a common technique for deriving a value of t
delivering high probability of success. In this case one that would
point to (3/2)^n * poly(n) with the 2/3 biased coin.
-- Owen
On May 4, 2010, at 4:30 PM, George Duncan wrote:
Owen,
Yes, you are right, it is (2/3)^n, call it p.
Then the probability of exactly 1 such happening in t repetitions
of the n-flip experiment is tp(1-p)^(t-1) (that's a binomial
probability),
or if you mean at least 1 happening, the probability is 1-(1-p)^t
(i.e., 1 - prob of no such happenings).
George
On Tue, May 4, 2010 at 4:18 PM, Owen Densmore <[email protected]>
wrote:
My probability is failing me. Could someone answer this?
I have a very biased coin that comes up 2/3 heads, 1/3 tails. I
want to do an experiment of n coin flips.
The probability that all are heads is (2/3)^n, right?
What I'm interested is the related question: Lets suppose I repeat
the experiment t times. How likely am I to get all heads once in a
series of t sets of n flips?
-- Owen
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org
--
George Duncan
georgeduncanart.com
represented by Artistas de Santa Fe
www.artistasdesantafe.com
(505) 983-6895
Life must be understood backwards; but... it must be lived forward.
Soren Kierkegaard
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org
