# Questions tagged [probability-theory]

Questions about the branch of mathematics concerned with modelling and analysing random phenomena.

429 questions
Filter by
Sorted by
Tagged with
33 views

### Is quantum computing a serious usable instrument for the IT industry?

Following this latest and very exciting research object I can't find till now a usable computer in that style. I would like to call actual quantum computing by the topic "researching of quantum ...
23 views

### Why does random noise in recurring task periods result in uniform period offsets?

I have a recurring task which finished just now. I schedule it to run every ten minutes; the task will reoccur $10n$ minutes from now for all positive $n$. If instead I choose 50/50 between ten ...
24 views

### Why is $\mathcal{D}^m(\{S:L_{(\mathcal{D},f)}(A(S))\gt \epsilon\})\leq \mathcal{D}^m\left(\bigcup^4_{i=1}F_i\right)$ true?

I am studying the book "Understanding Machine Learning: From Theory to Algorithms". I am struggling to understand the solution to exercise 3 (2) on page 41. Exercise: An axis aligned ...
11 views

### Distributed Graph Consensus to fit a distribution?

$G$ is a strongly connected graph with nodes $V$ and edges $E$. Each node $v_i$ receives a sample $x_i$ from a Gaussian $\mathcal{N}(\mu,\sigma^2)$ with unknown mean and variance. The objective is for ...
27 views

### Given only the expected runtime of an algorithm, what can Markov's inequality tell us about its worst-case runtime?

The following is exercise 3.8 from the first edition of Mitzenmacher and Upfal's Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Suppose that we have an algorithm that ...
109 views

### Question about "with high probability"

An event that occurs with high probability is one whose probability depends on a certain number $n$ and goes to $1$ as $n$ goes to infinity, i.e. it can be made as close as desired to $1$ by making $n$...
88 views

### Satisfiable CNFs where each clause contains logarithmically many different literals

Studying for my finals in Complexity theory. This question comes up in different variants and it requires to use probability. A side note before, to be more clear: A CNF clause consists of $n$ clauses ...
22 views

### How long a graph random walk takes to hit every vertex?

I have a simply connected graph $G$. I start at a uniformly randomly chosen vertex, and from there, randomly walk through the graph by choosing a random edge to follow at each step. On average, how ...
32 views

### Computing a threshold function

Let $f$ be any function from $\{0, 1\}^{n}$ to $\{-1, 1\}$. For a given $f$, let us define another function $g_f$ as \begin{equation} g_f(x) = \sum_{x \in \{0, 1\}^{n}} f(x). \end{equation} Let us be ...
59 views

### Deriving a lower bound on the conditional entropy, conditioned on an event

I came across Lemma 19 in Certifying Equality With Limited Interaction, which states the following for jointly distributed random variables $Z$, $W$, where $Z$ takes values in $\{0,1\}^n$, and some ...
8 views

### expected value of map generate algorithm

I designed a program to create a map in my 2D game program. And I have three questions... algorithm: step1: ...
34 views

### A small question about generating random variable with geometric distribution

I was reading Professor Knuth's Volume 2 (page 136) about generating a geometrically distributed random variable $N$ (with $p$ as the probability of success). Basically, the idea is to generate a ...
149 views

### Count Sketch probability bound

I have been reading up on the Count Sketch algorithm, and I stumpled upon the Count Sketh algorithm explained in section 5 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf. Then, I ...
36 views

### Quicksort: Probability of an element being compared to fewer than $k$ pivot elements

Assume we want to use quicksort on some array $s$ with length $n$ consisting of only $n$ distinct elements. Let $S_{(1)},S_{(2)},\dots,S_{(n)}$ be the sorted order of the elements in $S$. Furthermore, ...
28 views

### Dynamic programming and probability - list of problems

Does anyone have a list of problems where you have to combine dynamic programming with probability?
77 views

39 views

### The probability that a person succeeds to pick the longest stick from a randomly ordered n sticks of distinct lengths following the optimal strategy?

To begin with, consider two persons(Px and Py) are playing a game. Px is the organiser of the game who has n sticks of distinct lengths and displaying them one by one to Py in a random order, with ...
16 views

21 views

### Deterministic algorithms for computational distance between distributions

Computational distance between sequences of distributions $\{X_i\}_{i \in \mathbb{N}}$ and $\{Y_i\}_{i \in \mathbb{N}}$ can be defined as the maximum, over all probabilistic polynomial time algorithms ...
45 views

### oone exmple in hash topics?

Example: Suppose $H:${$1,...,n$} $\rightarrow${$1,..,n$} be a uniform hash function. for input $x$, $z$ is equal to number of trailing zero in the right side of $H(x)$. for $0 \leq c \leq 1$ what is ...
50 views

### Optimal algorithm to distinguish given black box access

This is a variant of this question. Consider two probability distributions $D$ and $U$, over $n$-bit strings, where $U$ is the uniform distribution. Assume that $D$ and $U$ are far apart in total ...
38 views

### How to implement conditional probability distribution on set-valued Random Variables

I'm trying to implement conditional probability distribution when the events of two RVs are sets. If I try to extrapolate concepts from real or categorical variables to sets things become confusing ...
35 views

Consider two probability distributions $D$ and $U$, over $n$-bit strings, where $U$ is the uniform distribution. We are not given an explicit description of $D$: we are only given black-box access, ie,...
33 views

### On the probability of randomized testing covering all combinatorial testing interactions

I'm interested in how fuzz testing and something called combinatorial testing. Combinatorial testing attempts to forgo exhaustive testing in favor of trying to test all possible "interactions&...
120 views

### Transition Function in MDP

I got a question about who and how sets the transation function values in markov decision processes? I mean when some says that an agent, in real world grid, is going to step up by %80 and left/right ...
36 views

### Distinguishability of distributions that are not close given just one sample

Consider (over $n$-bit strings) the uniform distribution $U$, and another distribution $D$ such that \begin{equation} \text{Distance}(D, U) \geq \frac{1}{e}, \end{equation} where $\text{Distance}$ ...
28 views

### Notation within gaussian function

On our lecture slides we have two different notations of the gaussian function. First it gets introduced as follows: p(x_n|\theta) = \frac{1}{\sqrt{2\pi}\sigma}exp\{-\frac{(x_n-\mu)^2}{2\sigma^2}\} \...
43 views

### Indistinguishability of exponentially close distributions

Let $D_{1}$ and $D_{2}$ be two probability distributions over $n$-bit strings such that the total variation distance between them is $\mathcal{O}\left(1/{2^{n}}\right)$. Given as input a polynomial ...
Assume we have n people with names: $h1, h2, ... , hn$ and they are going to shake hands with each other. The chance for every pair to shake hands is $0.6$. define $T$ the count of distinct triads of ...
I am looking for a family of pairwise independent hash functions $\mathcal{H} = \{h \mid h:[n]\rightarrow [m]\}$ that is easily computable. As an example that doesn't seem to work, choose a prime \$p &...