|
|
| Author |
Message |
un student
science forum addict
Joined: 21 Jan 2006
Posts: 80
|
 Posted: Wed Jun 14, 2006 4:32 pm Post subject:
A net with a probability
|
|
|
I had an exam today which had following assignment. (Writing it fully
out from memory so there could be some mistakes) Right after the
assignment is (a skeleton of) my solution. Could I have some comments
on it?
Let G(n,p), n in N, 0 < p < 1, be a model with Dom(G(n,p)) = {i | i in
N, 0 <= i < n } and p is the probability that elements i and i+1, 0 <=
i < n-1, have an edge between them. That is G(n,p) is a net like
*--*--*--*--*
where * is an element and -- is an edge which exists with probability
of p independetly of the other edges.
Let P(G(n,p)) be the probability that G(n,p) has two nodes with a
distance of 3 edges between them.
What is P(G)=lim_{n to infty} P(G(n,p))?
After a while I came up with the following idea.
Suppose P(G) is not one. Say it is 0 <= q < 1. Now, take four
consecutive elements from Dom(G(n,p)) (i, i+1, i+2, i+3). Now if there
is an edge between (i,i+1) and also between (i+1,i+2) then we could
reason there exists and edge between (i+2, i+3) with probability of
p*q. Right? But then the edge between (i+2, i+3) would not exists there
independetly of the other possible edges and hence q can not be 0 <= q
< 1 and so it must be one.
Is this idea correct? |
|
| Back to top |
|
 |
Brian M. Scott
science forum Guru
Joined: 10 May 2005
Posts: 332
|
| Posted: Wed Jun 14, 2006 8:43 pm Post subject:
Re: A net with a probability
|
|
|
On 14 Jun 2006 09:32:01 -0700, un student
<un.student@gmail.com> wrote in
<news:1150302721.502816.61710@h76g2000cwa.googlegroups.com>
in alt.math.undergrad:
| Quote: | I had an exam today which had following assignment. (Writing it fully
out from memory so there could be some mistakes) Right after the
assignment is (a skeleton of) my solution. Could I have some comments
on it?
Let G(n,p), n in N, 0 < p < 1, be a model with Dom(G(n,p))
= {i | i in N, 0 <= i < n } and p is the probability that
elements i and i+1, 0 <= i < n-1, have an edge between
them. That is G(n,p) is a net like
*--*--*--*--*
where * is an element and -- is an edge which exists with
probability of p independetly of the other edges.
Let P(G(n,p)) be the probability that G(n,p) has two nodes
with a distance of 3 edges between them.
What is P(G)=lim_{n to infty} P(G(n,p))?
After a while I came up with the following idea.
Suppose P(G) is not one. Say it is 0 <= q < 1. Now, take
four consecutive elements from Dom(G(n,p)) (i, i+1, i+2,
i+3). Now if there is an edge between (i,i+1) and also
between (i+1,i+2) then we could reason there exists and
edge between (i+2, i+3) with probability of p*q. Right?
|
I don't see any justification for this; can you explain in
more detail what you were thinking?
| Quote: | But then the edge between (i+2, i+3) would not exists
there independetly of the other possible edges and hence
q can not be 0 <= q < 1 and so it must be one.
Is this idea correct?
|
I don't think so, but I may be missing something.
Here's the first idea that occurs to me. Consider
G(3n+1,p). For 0 <= j < n let I(j) = {3j, 3j+1, 3j+2,
3j+3}. Say that I(j) is _good_ if it's the set of vertices
of a 3-chain. The probability that I(j) is good is p^3, so
the probability that I(j) is not not good is 1 - p^3, the
probability that *no* I(j) is good is (1 - p^3)^n, and the
probability that at least one I(j) is good is
1 - (1 - p^3)^n. Clearly P(G(3n+1,p)) >= 1 - (1 - p^3)^n,
and lim_{n -> infty} [1 - (1 - p^3)^n] = 1, since p > 0.
This shows that if the limit exists, it must be 1. It
doesn't actually show that the limit exists, but that
follows from the observation that for all n, P(G(n,p)) <=
P(G(n+1,p).
Brian |
|
| Back to top |
|
|
Brian M. Scott
science forum Guru
Joined: 10 May 2005
Posts: 332
|
| Posted: Thu Jun 15, 2006 5:40 am Post subject:
Re: A net with a probability
|
|
|
On Wed, 14 Jun 2006 16:43:24 -0400, "Brian M. Scott"
<b.scott@csuohio.edu> wrote in
<news:mlj1pz8bt5f3.nlmpskt95e9m$.dlg@40tude.net> in
alt.math.undergrad:
| Quote: | On 14 Jun 2006 09:32:01 -0700, un student
un.student@gmail.com> wrote in
news:1150302721.502816.61710@h76g2000cwa.googlegroups.com
in alt.math.undergrad:
I had an exam today which had following assignment.
(Writing it fully out from memory so there could be some
mistakes) Right after the assignment is (a skeleton of)
my solution. Could I have some comments on it?
Let G(n,p), n in N, 0 < p < 1, be a model with Dom(G(n,p))
= {i | i in N, 0 <= i < n } and p is the probability that
elements i and i+1, 0 <= i < n-1, have an edge between
them. That is G(n,p) is a net like
*--*--*--*--*
where * is an element and -- is an edge which exists with
probability of p independetly of the other edges.
Let P(G(n,p)) be the probability that G(n,p) has two nodes
with a distance of 3 edges between them.
What is P(G)=lim_{n to infty} P(G(n,p))?
After a while I came up with the following idea.
Suppose P(G) is not one. Say it is 0 <= q < 1. Now, take
four consecutive elements from Dom(G(n,p)) (i, i+1, i+2,
i+3). Now if there is an edge between (i,i+1) and also
between (i+1,i+2) then we could reason there exists and
edge between (i+2, i+3) with probability of p*q. Right?
I don't see any justification for this; can you explain in
more detail what you were thinking?
But then the edge between (i+2, i+3) would not exists
there independetly of the other possible edges and hence
q can not be 0 <= q < 1 and so it must be one.
Is this idea correct?
I don't think so, but I may be missing something.
Here's the first idea that occurs to me. Consider
G(3n+1,p). For 0 <= j < n let I(j) = {3j, 3j+1, 3j+2,
3j+3}. Say that I(j) is _good_ if it's the set of vertices
of a 3-chain. The probability that I(j) is good is p^3, so
the probability that I(j) is not not good is 1 - p^3, the
probability that *no* I(j) is good is (1 - p^3)^n, and the
probability that at least one I(j) is good is
1 - (1 - p^3)^n. Clearly P(G(3n+1,p)) >= 1 - (1 - p^3)^n,
and lim_{n -> infty} [1 - (1 - p^3)^n] = 1, since p > 0.
This shows that if the limit exists, it must be 1. It
doesn't actually show that the limit exists, but that
follows from the observation that for all n, P(G(n,p)) <=
P(G(n+1,p)).
|
In fact, I believe that the P(G(n,p)) satisfy the following
recurrence. For convenience let q(n) = P(G(n,p)). Then:
q(1) = q(2) = q(3) = 0
q(4) = p^3
q(n+1) = q(n) + p^3 * (1 - p) * (1 - q(n-3)) for n > 4
Since q(n-3) <= 1, q(n+1) >= q(n).
Brian |
|
| Back to top |
|
|
un student
science forum addict
Joined: 21 Jan 2006
Posts: 80
|
| Posted: Thu Jun 15, 2006 7:44 am Post subject:
Re: A net with a probability
|
|
|
Brian M. Scott wrote:
| Quote: | On 14 Jun 2006 09:32:01 -0700, un student
....
Let P(G(n,p)) be the probability that G(n,p) has two nodes
with a distance of 3 edges between them.
What is P(G)=lim_{n to infty} P(G(n,p))?
After a while I came up with the following idea.
Suppose P(G) is not one. Say it is 0 <= q < 1. Now, take
four consecutive elements from Dom(G(n,p)) (i, i+1, i+2,
i+3). Now if there is an edge between (i,i+1) and also
between (i+1,i+2) then we could reason there exists and
edge between (i+2, i+3) with probability of p*q. Right?
I don't see any justification for this; can you explain in
more detail what you were thinking?
|
My thinking was simply that if q is not one we could use it to
calculate probabilities of some edges (k,k+1) if we knew something
about the edges before k. That is, if q is not one the probability of
edge in (k,k+1) would not be always independet of the other edges.
We would come to situation where P(A & B) != P(A) * P(B). I can't
recall the exact answer I gave, but this is the main idea used... Could
be that the exact solution I gave is not presented accurately enough
but I don't see what's wrong with the idea.
....
| Quote: | 1 - (1 - p^3)^n. Clearly P(G(3n+1,p)) >= 1 - (1 - p^3)^n,
and lim_{n -> infty} [1 - (1 - p^3)^n] = 1, since p > 0.
|
That's a pretty clear way to do it. |
|
| Back to top |
|
|
Brian M. Scott
science forum Guru
Joined: 10 May 2005
Posts: 332
|
| Posted: Thu Jun 15, 2006 8:00 am Post subject:
Re: A net with a probability
|
|
|
On 15 Jun 2006 00:44:19 -0700, un student
<un.student@gmail.com> wrote in
<news:1150357459.153674.21850@p79g2000cwp.googlegroups.com>
in alt.math.undergrad:
| Quote: | Brian M. Scott wrote:
On 14 Jun 2006 09:32:01 -0700, un student
...
Let P(G(n,p)) be the probability that G(n,p) has two nodes
with a distance of 3 edges between them.
What is P(G)=lim_{n to infty} P(G(n,p))?
After a while I came up with the following idea.
Suppose P(G) is not one. Say it is 0 <= q < 1. Now, take
four consecutive elements from Dom(G(n,p)) (i, i+1, i+2,
i+3). Now if there is an edge between (i,i+1) and also
between (i+1,i+2) then we could reason there exists and
edge between (i+2, i+3) with probability of p*q. Right?
I don't see any justification for this; can you explain in
more detail what you were thinking?
My thinking was simply that if q is not one we could use
it to calculate probabilities of some edges (k,k+1) if we
knew something about the edges before k.
|
I understood that that was your idea; I just don't see how
this could be done.
| Quote: | That is, if q is not one the probability of edge in
(k,k+1) would not be always independet of the other
edges.
We would come to situation where P(A & B) != P(A) * P(B).
I can't recall the exact answer I gave, but this is the
main idea used... Could be that the exact solution I gave
is not presented accurately enough but I don't see what's
wrong with the idea.
|
The problem is that I don't see any way to justify the claim
that if there are edges (i, i+1) and (i+1, i+2), then the
probability that there's an edge (i+2, i+3) is pq. I agree
that if you could do that, you'd be done, but I don't see
any way to do it.
[...]
Brian |
|
| Back to top |
|
|
un student
science forum addict
Joined: 21 Jan 2006
Posts: 80
|
| Posted: Thu Jun 15, 2006 8:56 am Post subject:
Re: A net with a probability
|
|
|
Brian M. Scott wrote:
| Quote: | On 15 Jun 2006 00:44:19 -0700, un student
My thinking was simply that if q is not one we could use
it to calculate probabilities of some edges (k,k+1) if we
knew something about the edges before k.
I understood that that was your idea; I just don't see how
this could be done.
|
Ok.
| Quote: |
That is, if q is not one the probability of edge in
(k,k+1) would not be always independet of the other
edges.
We would come to situation where P(A & B) != P(A) * P(B).
I can't recall the exact answer I gave, but this is the
main idea used... Could be that the exact solution I gave
is not presented accurately enough but I don't see what's
wrong with the idea.
The problem is that I don't see any way to justify the claim
that if there are edges (i, i+1) and (i+1, i+2), then the
probability that there's an edge (i+2, i+3) is pq. I agree
that if you could do that, you'd be done, but I don't see
any way to do it.
|
Hmm. I'm starting to doubt my logic.
Edge (i,i+1) exists with probability p for all i. If the probability
that there exists two nodes with distance of 3 edges between is q then
the probability that four random consecutive elements picked (i, i+1,
i+2, i+3) has all three possible edges is q. Right?
For me it looks that p and q are independent of each other. Aren't
they?
If we take a look at picked elements and find out there are edges (i,
i+1) and (i+1, i+2) then we could say that edge (i+2,i+3) exists if
both p and q happen. If we had chosen elements which don't satisfy the
condition then edge (i+2, i+3) wouldn't exists(?). So we have to have
both p and q.... no, this is incorrect. It exists with prob. p or q
which doesn't make much sense.
I see... Oh well, lesson learned...
Thanks! |
|
| Back to top |
|
|
Brian M. Scott
science forum Guru
Joined: 10 May 2005
Posts: 332
|
| Posted: Thu Jun 15, 2006 9:13 am Post subject:
Re: A net with a probability
|
|
|
On 15 Jun 2006 01:56:32 -0700, un student
<un.student@gmail.com> wrote in
<news:1150361792.491933.41360@p79g2000cwp.googlegroups.com>
in alt.math.undergrad:
| Quote: | Brian M. Scott wrote:
|
[...]
| Quote: | The problem is that I don't see any way to justify the claim
that if there are edges (i, i+1) and (i+1, i+2), then the
probability that there's an edge (i+2, i+3) is pq. I agree
that if you could do that, you'd be done, but I don't see
any way to do it.
Hmm. I'm starting to doubt my logic.
Edge (i,i+1) exists with probability p for all i. If the
probability that there exists two nodes with distance of
3 edges between is q then the probability that four
random consecutive elements picked (i, i+1, i+2, i+3) has
all three possible edges is q. Right?
|
There's your problem. No, this isn't true. Even if
(i, i+1, i+2, i+3) isn't a 3-chain, the graph may still have
a 3-chain somewhere else. The probability that G(n,p) has a
3-chain somewhere is greater than the probability that it
has one starting at a particular i. (And the probability
that it has one starting at i is p^3 if i < n - 3 and 0
otherwise.)
[...]
My pleasure: this was an interesting problem!
Brian |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Sat Jan 10, 2009 2:44 am | All times are GMT
|
|
Bankruptcy | Mobile Phone | Mortgage insurance | Xbox Mod Chips | Bad Credit Mortgages
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
Undergraduate
