A random graph

First, we want to compute the expected number of increment of vertices for the $n$ th iteration.

For example, for the 1st iteration (i.e growth from 1 -> 3 vertices), the expected number of vertices increment is $3 \times (1-p)$ .

For the second iteration, the expected number of vertices increment is $(3 \times (1-p))^2$ . This continues on, and so for the $n$ th iteration, the we have the expected number of vertices increment to be $(3 \times (1-p))^n$ .

Therefore, let $X$ be the total number of vertices increment, and $X_1, X_2,\ldots,X_n$ denote the vertices increment in the $n$ th iteration. We know that the expected number of vertices is 100, so:

$100$

$= 1 + E(X)$

$= 1 + E(X_1)+E(X_2)+\cdots+E(X_n) + \cdots$

$= 1+ \frac{3 \times (1-p)}{1-3 \times (1-p)}$ .

The last step was through application for the infinite sum of a geometric progression, because $E(X_1)+E(X_2)+\cdots+E(X_n) + \cdots$ is a geometric series sum with first term = $3 \times (1-p)$ and common ratio = $3 \times (1-p)$ .

Solving for $p$ , we get $p = \frac{67}{100}$ .

Therefore $a+b = 167$ .

Assuming the start time is 0 , and the algorithm processes 1 step by time 1 passes.

On time $t$ , the graph has a possibility to constructs $3^t$ new vertices.

The birth probability of each vertex is $(1-p)^t$ .

So

$Exp = \displaystyle \sum_{t=0}^\infty 3^t * (1-p)^t = \frac {1}{1 - 3(1-p)}$ (when $p > \frac{2}{3}$ .)

Now $Exp = 100$ . Then We get $p = \frac{67}{100}$ .

Giving the answer of $a+b=167$ .

Let $V$ be the number of vertices in the graph.

There is a $p$ probability that the graph stops with $1$ vertex.

There is a $1-p$ probability that the graph has the original $1$ vertex and three "branches" with $V_1,V_2,V_3$ vertices.

Therefore, $E[V] = p \cdot 1 + (1-p) \cdot (1+E[V_1+V_2+V_3])$ $= 1 + (1-p)(E[V_1]+E[V_2]+E[V_3])$ .

The process to generate each of the 3 branches is identical to the process to generate the overall graph. Thus, $E[V_1] = E[V_2] = E[V_3] = E[V] = 100$ .

Thus, the equation becomes: $100 = 1 + (1-p) \cdot 300$ .

Solving yields $p = \dfrac{67}{100} = \dfrac{a}{b}$ . Since $\gcd(67,100) = 1$ it follows that $a = 67$ , $b = 100$ , and $a+b = 167$ .

Let $E(p)$ be the expected number of vertices of the graph for probability p.

At the first step, a vertex is always created. With probability p, we stop there. If not, we are essentially initiating three versions of our original problem since vertices are added or not to existing vertices independently. Using linearity of expectation, we obtain $E(p)=1+3(1-p)E(p)$

This has the solution $E(p)=\frac{1}{3p-2}$ . Setting $E(p)=100$ gives us $p=\frac{67}{100}$ .

Now, we need to make sure that this answer is really meaningful. For example, if $p$ were zero, $E(p)$ is really infinite since the procedure never stops, but our foumula would give us $E(p)=-\frac{1}{2}$ which is meaningless.

Thus we need to show that the procedure is expected to terminate for $p=\frac{67}{100}$ . Assume that the number of newly created vertices at a given stage is $N$ . Then the expected number of newly created vertices at the next stage is $3N(1-p)$ . For the procedure to be expected to terminate, we need $3N(1-p)\le N$ . That is, $p\ge \frac{2}{3}$ . Since $\frac{67}{100}\ge\frac{2}{3}$ , we are done.

Expected number of new Nodes = E

E = p * 0 + (1-p) * (3 + 3 E); aw with 1-p probability we have 3 nodes and each will have E as its expected new nodes.

E = 99( given total node = 100, so expected number of new nodes = 99)

99* ( 3p -2) = 3 - 3p

p = 201/300 = 67/100

a = 67, b =100 ; a+b = 167

Expected number of vertices in graph = 1+(1-p) 3+(1-p)^2 *3^2+...... This forms a GP with r=(1-p) 3, It is given that Expected number of vertices in graph is 100. So , 100= 1+(1-p) 3+(1-p)^2 *3^2+...... 100=1+ (1-p) 3/(1-(1-p) 3) . 3-3 p=99-297(1-p) . 3-3 p=99-297+297 p . 300-99=300*p . p=201/300=67/100=a/b . a+b=67+100=167

The expected number of vertices $e(p)$ satisfies

$e(p) = p(1) + (1-p)(1 + 3 e(p))$ .

Setting $e(p) = 100$ , and solving for $p$ ,. we get $p = 67/100$ .

Let $E$ be the expected number of vertices in the graph. With probability $p$ , the graph has 1 vertex, and with probability $1-p$ , we have the initial vertex and repeat this process on 3 more vertices, so the expected number of vertices will be $1 + 3E.$ This gives the relation

$\begin{aligned} E & = p + (1-p)(1 + 3E)\\ E & = p + 1 - p + 3E(1-p)\\ E & = 1 + 3E - 3Ep\\ 1 + 2E & = 3Ep\\ p & = \frac{1+2E}{3E}\ \end{aligned}$

When $E = 100$ , we get $p = \frac{67}{100}$ , so $a + b = 67 + 100 = 167.$

For the simplicity of calculation, let $m = 1 - p$ , i.e. let $m$ be the probability that more vertices are constructed and let $1 - m$ be the probability that no more vertices are constructed. From inspection, it becomes clear that if no additional vertices are constructed then there are $3^0 = 1$ vertices; if additional vertices are constructed once then there are $3^0 + 3^1 = 4$ vertices; and, generally, if additional vertices are constructed $n$ times then there are $\displaystyle \sum_{i=0}^{n} 3^i$ vertices.

Next, we must apply the probability of obtaining each outcome, multiply it by the outcome's respective number of vertices, and add everything together to find what value of $m$ will make the expected value be $100$ . So, the expected value is $1(1 - m) + 4(m)(1 - m) + 13(m^2)(1-m) + 40(m^3)(1-m) + ...$ , which equals $100$

This series is geometric. By expanding each term, we come to the following: $1 + 3m + 9m^2 + 27m^3 + ...$ , an infinite geometric series with $r = 3m$ and $t_1 = 1$

> Since the $kth$ term is $\displaystyle \sum_{i=1}^{k} 3^{i-1} * (m^{i-1} - m^i)$ and the $k + 1th$ term is $\displaystyle \sum_{i=1}^{k+1} 3^{i-1} * (m^{i-1} - m^{i})$ , the second part of the $kth$ term added to the first part of the $k + 1th$ term will always result in $3^{k} m^{k}$ . Therefore, the series is telescopic and the trend continues.

Using the formula for the sum of convergent geometric series, we come to $\frac {1}{1 - 3m} = 100 \rightarrow m = \frac {33}{100} \rightarrow p = \frac {67}{100} \Rightarrow a + b = 167$

Let $X$ be the number of vertices of the graph. At the 0-th stage of the process we have just one vertex. The probability that the process stops there, is given by $P(X = 1) = p.$ Each time, new edges grow at all the vertices created at the previous stage with probability $(1-p)$ . Hence the process will stop at the k-th stage with probability $p(1-p)^k$ . At this stage we have $1 + 3 + 3^2 + … + 3^k = \frac{3^{k+1}-1}{3-1} = \frac12 \left(3^{k+1} -1\right)$ vertices. Thus: $P(X = \frac12(3^{k+1} -1)) = p (1-p)^k.$ The expected number of vertices is $EX = \Sigma_{k = 0}^\infty \frac12 \left(3^{k+1} - 1\right) p (1-p)^k$ $= \frac12 p \left( \Sigma_{k = 0}^\infty 3^{k+1} (1-p)^k - \Sigma_{k = 0}^\infty (1-p)^k \right)$ $= \frac12 p \left(3 \cdot \Sigma_{k = 0}^\infty \left(3 (1-p)\right)^k - \frac1{p} \right)$ $= \frac{3p}{2(3p-2)} - \frac12 = \frac1{3p-2}.$ The expected number of vertices is 100. We have to solve $\frac1{3p-2} = 100.$ We thus obtain $p = 67/100$ .