Questions tagged [randomized-algorithms]
an algorithm that employs a degree of randomness as part of its logic.
7
questions
2
votes
1answer
116 views
Why does Hutchinson's trace estimator reduce computation complexity?
Given a matrix $A$, we want to compute its trace, in which we can use a trick name Hutchinson's trace estimator
\begin{align}
tr(A) = tr(A\mathbb{E}[\epsilon \epsilon^T])=\mathbb{E}[tr(A \epsilon \...
0
votes
0answers
16 views
What is the order a randomized membership algorithm?
Suppose we have two sets $S$ and $I$, where $|S|=n$ and $|I|=0$. I use a randomized algorithm to add all of the members of $S$ to another set $I$. Each iteration of the algorithm has two steps. In the ...
0
votes
0answers
152 views
Why is DP-SGD differentially private?
The paper 'Deep Learning with Differential Privacy' explains how to make a deep learning algorithm as differentially private. This explanation is implemented in Tensorflow Privacy
My question is: we ...
2
votes
1answer
28 views
Survey Analysis: Weighted Randomization to fill Missing Values
I am developing a Survey Analysis Application that works with Categorical Data and looking for a way to treat missing data fairly without losing the original data variance.
Thus, I came up with a way ...
1
vote
0answers
20 views
With high probability analysis
I am quite confused with 'with high probability analysis' in randomized algorithms. Perhaps it's helpful to illustrate with an example. What is the expected number of rounds to have at least one head ...
0
votes
1answer
48 views
Is it possible to to have more than 2 groups for biased coin randomization? If no, is there any modifications supporting multiple groups?
Is it possible to have more than 2 groups for biased coin randomization?
If no, is there any modifications of biased coin randomization supporting multiple groups?
This is my R code for generating ...
2
votes
1answer
26 views
Why $Pr[X-\mu \geq t]= Pr[e^{\lambda(X-\mu)} \geq e^{\lambda t}]$ for all $\lambda> 0$
I hope everyone is having a nice day. I don't know why this inequality holds.
$$
Pr[X-\mu \geq t]= Pr[e^{\lambda(X-\mu)} \geq e^{\lambda t}]
$$
For $\lambda >0$. I guess it has something to do ...
