Homework!
Locked
 
Administrator
|
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 |
|
|
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 <[hidden email]> wrote: My probability is failing me. Could someone answer this? -- 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 |
|
|
In reply to this post by Owen Densmore
On 4 May 2010 at 16:18, Owen Densmore 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? Exactly once, or at least once? ============================================================ 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 |
|
Administrator
|
At least once, now that I think about it.
-- Owen On May 4, 2010, at 4:58 PM, [hidden email] wrote: > On 4 May 2010 at 16:18, Owen Densmore 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? > > Exactly once, or at least once? > > ============================================================ > 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 |
|
Administrator
|
In reply to this post by George Duncan-2
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:
============================================================ 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 |
|
Administrator
|
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:
============================================================ 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 |
«
Return to Friam
|
1 view|%1 views
| Free forum by Nabble | Edit this page |