Branching process, inductive proof

In summary: G_k(s)=\frac{1-2^k-2(1-2^{k-1})s}{1-2^{k+1}-2(1-2^k)s}Therefore, the statement is also true for n=k+1. By induction, we can conclude that the statement is true for all n. In summary, we have proven by induction that G_n(s)=\frac{1-2^n-2(1-2^{n-1})s}{1-2^{n+1}-2(1-2^n)s}. This may seem like a tedious question, but it is important to
  • #1
spitz
60
0

Homework Statement



Assume that the the offspring distribution is [itex]P(Y=y)=\left(\frac{1}{2}\right)^y\frac{1}{3}[/itex]
[itex]y=0,1,2,\ldots[/itex]

Show by induction that:

[tex]G_n(s)=\frac{1-2^n-2(1-2^{n-1})s}{1-2^{n+1}-2(1-2^n)s}[/tex]

2. The attempt at a solution

I can see that the distribution is geometric so:

[tex]G(s)=\frac{p}{1-qs}=\frac{1}{3-2s}[/tex]

I assume I have to show that:

[tex]G_{n+1}(s)=\frac{1-2^n-2(1-2^{n-1})\frac{1}{3-2s}}{1-2^{n+1}-2(1-2^n)\frac{1}{3-2s}}[/tex]

equals:

[tex]\frac{1-2^{n+1}-2(1-2^{n})s}{1-2^{n+2}-2(1-2^{n+1})s}[/tex]

The thing is, this seems like kind of a tedious question considering the amount of marks I'll get for it on my exam. Am I missing something here? Is there a "quick" way to do this?
 
Physics news on Phys.org
  • #2


Hello!

First of all, I would like to clarify that the given distribution is not geometric, it is a negative binomial distribution. The geometric distribution has a fixed probability of success (p) for each trial, while the negative binomial distribution has a fixed number of successes (r) for a given number of trials (n).

Now, to prove the given statement by induction, we first need to establish the base case. For n=1, we have:

G_1(s)=\frac{1-2^1-2(1-2^0)s}{1-2^{1+1}-2(1-2^1)s}=\frac{1-2-2(1-1)s}{1-4-2(1-2)s}=\frac{1-2s}{1-2s}=1

Therefore, the statement is true for n=1.

Now, let's assume that the statement is true for n=k, i.e. G_k(s)=\frac{1-2^k-2(1-2^{k-1})s}{1-2^{k+1}-2(1-2^k)s}.

We need to prove that the statement is also true for n=k+1, i.e. G_{k+1}(s)=\frac{1-2^{k+1}-2(1-2^{k})s}{1-2^{k+2}-2(1-2^{k+1})s}.

We have:

G_{k+1}(s)=\frac{1-2^{k+1}-2(1-2^{k})s}{1-2^{k+2}-2(1-2^{k+1})s}=\frac{1-2^{k+1}-2(1-2^{k})s}{1-2^{k+1}-2(1-2^{k})s-2(1-2^{k+1})s}=\frac{1-2^{k+1}-2(1-2^{k})s}{1-2^{k+1}-2(1-2^{k})s-2+4^{k+1}s}=\frac{1-2^{k+1}-2(1-2^{k})s}{1-2^{k+1}-2(
 

1. What is a branching process?

A branching process is a mathematical concept used to model the growth and development of a population or system over time. It involves a sequence of events, where each event has a certain probability of resulting in multiple new events, or branching out.

2. How is branching process related to inductive proof?

Branching process is closely related to inductive proof because it relies on the principle of induction to make predictions about the future behavior of the system. Inductive proof involves using observations and patterns to make generalizations and predictions, which is also the basis of branching process.

3. What is the role of probability in branching process?

Probability plays a crucial role in branching process as it determines the likelihood of an event branching out into multiple events. The branching process model uses probability to calculate the expected number of offspring in each generation, which is used to predict the future behavior of the system.

4. Can branching process be applied to real-life situations?

Yes, branching process can be applied to real-life situations in various fields such as biology, economics, and computer science. For example, it can be used to model the spread of diseases in a population, the growth of a company, or the development of a computer program.

5. What are some limitations of branching process?

One limitation of branching process is that it assumes a constant probability of branching for each event, which may not always hold true in real-life situations. It also does not take into account external factors that may affect the growth and development of the system. Additionally, branching process is a simplified model and may not accurately reflect the complexity of certain systems.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
93
  • Calculus and Beyond Homework Help
Replies
15
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
126
  • Calculus and Beyond Homework Help
Replies
4
Views
751
  • Calculus and Beyond Homework Help
Replies
4
Views
636
  • Calculus and Beyond Homework Help
Replies
3
Views
637
  • Calculus and Beyond Homework Help
Replies
1
Views
458
  • Calculus and Beyond Homework Help
Replies
2
Views
154
  • Calculus and Beyond Homework Help
Replies
3
Views
503
  • Calculus and Beyond Homework Help
Replies
3
Views
467
Back
Top