People who code: we want your input. Take the Survey

# Tag Info

## New answers tagged probabilistic-algorithms

1

The probability that the maximum rank $r_{\max}$ is at most $m$ is $$(1 - q_{1m}) \cdots (1 - q_{nm}),$$ where $$q_{km} = \binom{k-1}{m} \bigg/ \binom{n}{m}.$$ Therefore  \mathbb{E}[r_{\max}] = \sum_{m=1}^n \Pr[r_{\max} \geq m] = \sum_{m=1}^n (1 - \Pr[r_{\max} \leq m-1]) = \\ 1 + \sum_{m=1}^{n-1} \left[1 - \prod_{k=1}^n \left(1 - \binom{k-1}{m}\bigg/\...

0

The following answer construct a tester for a graph being complete $\ell$-partite for a fixed value of $\ell$. Consider the following tester: Choose $\ell+1$ vertices at random. Verify that the edges between them are consistent with a complete $\ell$-partite graph, that is, there is a way to color the vertices using $\ell$ colors such that there is an edge ...

0

I came up with this answer which can approximately sample a bivariate normal distribution with accept reject method and I thought it might be useful for others in future. we choose a 2D uniform distribution called $F_{X,Y}(x,y) = F_X(x).F_Y(y)$ where both $X$ and $Y$ are uniform distributions in range of $(0, +a)$ and they are independent of each other. We ...

0

You can use search on this site to find some examples: https://cs.stackexchange.com/search?q=%5Bdynamic-programming%5D+probability

Top 50 recent answers are included