Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [pr.probability]

Questions in probability theory

245 questions
Filter by
Sorted by
Tagged with
134 views

### Parity of the sum of pseudorandom bits over a non-sparse set of inputs

Suppose I have a pseudorandom function (in the theoretical sense) $X\colon\{0,1\}^{n+m}\rightarrow\{0,1\}$ (where $m$ is polynomial in $n$) and a non-empty set $S\subseteq\{0,1\}^m$ ($S$ is not sparse,...
• 369
367 views

• 109
55 views

### Amplifying success probability for PTMs with $poly(n) / \exp(n)$ gap?

The following is a well-known result of BPP in complexity theory, e.g., Theorem 1 and its proof from here: Consider a probabilistic Turing Machine (PTM) $M$, and a language $L \in BPP$: If $x \in L$ (...
53 views

### Approximately sampling from a discrete unimodal distribution with large support

I have an algorithmic problem and I am curious if a solution is known in the literature, because I cannot find it. I came up with an algorithm of my own, but would be curious if something is known. I ...
• 630
47 views

• 265
47 views

### understanding generalized coupon collector for distributions or learning mixture of distribution

Lets suppose we have a set $S=\{1,\ldots,n\}$ and $P$ is the uniform distribution over two subsets $T_1,T_2\subseteq S$, each of size $m\leq n/100$. Now, suppose somehow is given uniform samples from ...
• 251
67 views

### Notation in proof for Asymptotic Equipartition Property

In the following lecture notes chapter 3, page 12-13, they state the following We begin by introducting some important notation: - For a set $\mathcal{S},|\mathcal{S}|$ denotes its cardinality (...
• 133
202 views

### Binary search on coin heads probability

Let $f:[0,1] \to [0,1]$ be a smooth, monotonically increasing function. I want to find the smallest $x$ such that $f(x) \ge 1/2$. If I had a way to compute $f(x)$ given $x$, I could simply use ...
• 12.1k