MediumProbabilitypr-120

First Moment Method for Triangles

Problem

Expected number of triangles in the Erdos-Renyi graph G(n, p):

E[triangles] = C(n, 3) * p^3.

Each of the C(n, 3) triples forms a triangle independently with probability p^3. Return 0.0 for n < 3 or negative p.

Hint

Apply linearity of expectation over the C(n, 3) triples.

case 1

in: [4,0.5]

expected: 0.5

case 2

in: [10,0.5]

expected: 15

case 3

in: [3,1]

expected: 1

case 4

in: [2,0.5]

expected: 0

Starter codePython

import math


def first_moment_triangles(n, p):
    # Your code here
    pass

4 test cases · run your code against them in the editor