Search   Memberlist   Usergroups
 Page 1 of 1 [7 Posts]
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?
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
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
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.
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
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!
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.)

[...]

 Quote: Thanks!

My pleasure: this was an interesting problem!

Brian
Google

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [7 Posts]
 The time now is Sat Jul 09, 2011 1:56 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Probability Question dumont Probability 0 Mon Oct 23, 2006 3:38 pm probability gorbag Probability 0 Mon Aug 14, 2006 11:06 pm Probability of attaining a minimum value when rolling dice nick@blackmarble.co.uk Math 16 Tue Jul 18, 2006 2:57 pm A mathematical game - probability questions Alun Math 8 Sun Jul 16, 2006 12:25 pm convergence of probability measures pkg Math 0 Sat Jul 15, 2006 7:15 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters

Powered by phpBB © 2001, 2005 phpBB Group
 [ Time: 0.0444s ][ Queries: 16 (0.0034s) ][ GZIP on - Debug on ]