Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Ensure uniform sampling for randomized operations #44

Open
daemontus opened this issue Sep 8, 2023 · 0 comments
Open

Ensure uniform sampling for randomized operations #44

daemontus opened this issue Sep 8, 2023 · 0 comments

Comments

@daemontus
Copy link
Member

At the moment, the distributions with which valuations are sampled in randomized operations depends on the structure of the BDD. Instead, we should adjust the algorithm to ensure that the sampling is uniform across the valuations of the BDD.

Currently, the randomized operations use a "fair coin" to pick a variable value (i.e. each pick is equally likely). This over-represents results from branches with few valuations. To make this "uniform" across all valuations, the coin should be biased based on the number of valuations in each branch. We can easily compute this number of valuations (it's the same algorithm as for the total cardinality number). We just need to bias the coin correctly based on this number.

Nevertheless... it could be interesting to also provide different sampling strategies. Because sometimes, we don't actually want to be uniform. For example, we might rather sample from the more "extreme" values...

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant