# Questions tagged [pr.probability]

Questions in probability theory

200 questions
Filter by
Sorted by
Tagged with
260 views

316 views

656 views

251 views

### About a random walk with constant spectral gap

The existence of a graph with certain strange-looking properties will imply a counterexample to something I am playing with. I'm stuck on figuring out whether such a graph can exist and so I thought I'...
156 views

62 views

### Computing the distribution from which this algorithm samples from

Assume we have a set of integers $X_0=\{x_1\ge x_2\ge\ldots\ge x_n\}$. Let $r\in(0,1]$ be a parameter and consider the ranking process: i=0 while ($X_i\ne\emptyset$) let $M = \max \{x\in X_i\}$ (...
1k views

### Finding a biased coin using a few coin tosses

The following problem came up during research, and it's surprisingly clean: You have a source of coins. Each coin has a bias, namely a probability that it falls on "head". For each coin ...
648 views

### Sampling distinct values with probability proportional to their frequency

This is a variant of my previous question (Reservoir sampling of distinct values) I'm faced with a situation where I need to get m samples from a data stream (without replacement). Only one pass ...
531 views

146 views

### High-Probability bounds for Stochastic multi-armed Bandit Problems

This paper gives some high probability results for UCB algorithm of the form, \begin{align} \mathbb{P}(R_{n} > r_0.x) \leq O(n^{-2\rho x + 1} + x^{-2 \rho + 1} ) \end{align} where $\rho$ is a ...
210 views

193 views

### Probabilistic sorting given pairwise comparison probability

Let $X = \{x_1, \dots, x_n\}$ be a set, and $f:[1..n]^2 \to [0, 1]$ be a function, such that $$f(i, j) \cdot f(j, k) \le f(i, k)$$ For all $1 \le i, j, k \le n$. Does there exist a randomized ...
I have been working on privacy and come across a neat problem. Suppose two random variables $X$ and $Y$, over finite alphabets $\mathcal{X}$ and $\mathcal{Y}$, are given with joint distribution $P_{... 3answers 533 views ### Is there any known CCC closed under a probabilistic powerdomain operation? Equivalently, is there a known denotational semantics for probabilistic higher-order functional programming languages? Specifically, is there a domain model of pure untyped$\lambda$-calculus extended ... 0answers 126 views ### Strong Dependence I asked this question on MO, but no answer. I don't know if this definition has been already given. Suppose$X$and$Y$are two random variables over finite alphabets$\mathcal{X}$and$\mathcal{Y}$... 1answer 258 views ### What are bounded-treewidth circuits good for? One can talk of the treewidth of a Boolean circuit, defining it as the treewidth of the "moralized" graph on wires (vertices) obtained as follows: connect wires$a$and$b$whenever$b$is the output ... 3answers 1k views ### What is the expected depth of a randomly generated tree? I thought about this problem a long time ago, but have no ideas about it. The generating algorithm is as follows. We assume there are$n$discrete nodes numbered from$0$to$n - 1$. Then for each$i$... 1answer 99 views ### References to learn more about graph laplacian. I have vaguely heard of this connection between random matrix theory and graphs (the spectral gap of their laplacians) on compact Riemann surfaces. Can someone give a pedagogic reference which helps ... 0answers 124 views ### Spectrum of absorbing random walk for regular graphs I have a symmetric Markov chain given by the matrix$P$. Let$M$be a set of special states of the chain (called marked states, they correspond to solutions to some problem). We can write$P$as \... 0answers 251 views ### Probability distributions and computational complexity Some probability distributions are easier to work with than others. Consider the following two problems. Given a number$n$, return$i$with$0 \leq i < n$with uniform probability, i.e.$\mathbb{...
I am asking the question on a slightly abstract level and it may depend on the specifics but it would be great to have related references or ideas. Consider the random graph model $G_{n,p}$ where its ...