Discrete Applied Mathematics 377 (2025), 74-86.
The average expected value of a rooted graph, Monte Carlo calculation, and a power index for the voting
game
by Masahiro Hachimori
Abstract
The expected value of a rooted graph is the expected value of the number of vertices
reachable from the root when each edge is deleted independently with probability (1-p).
The uniform expected value of a rooted graph is the average of the expected value
assuming the probability p is taken uniformly at random from [0,1].
In this paper, after verifying that computing the uniform expected value of a rooted graph
is #-P-hard, we propose a Monte Carlo method for computing the uniform expected value.
We also discuss some applications of the proposed method for 0/1-valued monotone set functions.