# Questions tagged [pr.probability]

Questions in probability theory

202 questions
Filter by
Sorted by
Tagged with
45 views

### Is there a complete and finite axiom scheme for conditional independence? (Graphoids)

Note: This is a better-written version of an unanswered question asked before on MathOverflow. Question: Is there a complete and finite axiom scheme for conditional probability? If so, is there a ...
68 views

### Concentration Bounds for Thompson sampling

This paper gives concentration results around the mean of the regret for variants of UCB algorithm in multi-armed stochastic bandits. However, I could not find any similar results for Thompson ...
147 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 ...
111 views

### On a possible probabilistic log-rank conjecture

The communication matrix of a function $f$ is a $2^{n}\times 2^{n}$ matrix $M_f$ where the indices of the rows (columns) correspond to the inputs of Alice (Bob), and each entry $M_f (a,b)$ is the ...
127 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}$...
224 views

### What is the optimal strategy for this 2 player game?

Let some finite array of integers is given initially. There is a number k which is initially '0'. In a move, a player will select a number from the array arr[i] and change k to gcd(k,arr[i]). Also, ...
122 views

### How to find a merge tree for a set of words?

Consider a set $S \subseteq \Sigma^n$ where $\Sigma$ is a finite alphabet and $p : \Sigma \rightarrow [0,1]$ is a probability function. Let $T$ be a tree leaf-labeled by the elements of $S$. Consider ...
92 views

### Convergence of iterated stochastic matrices

(This question has been unsuccessfully asked on mathoverflow: https://mathoverflow.net/questions/161728/convergence-of-iterated-stochastic-matrices) It is well-known that for a stochastic aperiodic ...
92 views

### randomness extraction of real valued sequences of numbers

I have a sequence of numbers $x_1, x_2, \dots, x_n, \dots \in \mathbb{R}$ I would like to extract fair bits from that sequence. My first thought was to use the Von Neumann extractor. For a ...
2k views

### Calculate Huffman code length having probability?

Having an alphabet made of 1024 symbols, we know that the rarest symbol has a probability of occurrence equal to 10^(-6). Now we want to code all the symbols with Huffman Coding. How many bits will ...
940 views

### Chernoff Bounds for settings with limited dependence

Could someone point me to a way of bounding the tail probability of sums of bernoulli variables each generated by the same distribution but the condition of independence is only partially satisfied. ...
1k views

### question about probability ranking principle

I am studying IR and I am not clearly understand "probability ranking principle" ( I tried to google the definition, but i couldn't find clear answer.) I am assuming that it's system which ...
158 views

### Policy Adjustment in Markov Decision Process

I was using MDP on my work to make optimal decision. I used discrete time, finite state MDP. I assumed that I will have an initial parameters, like the Reward/Cost, state transition probabilities and ...
94 views

92 views

### Weighted circular balls into bins

I would like to ask you for a help about modified balls into bins problem. Consider $n$ weighted balls such that each ball has a weight $w_i$ that is at most $W$. Furthermore, each of $m$ bins has a ...
60 views

### Mapping of entire balls using Locality Sensitive Hashing (LSH)

LSH functions are useful for approximate nearest neighbor search. They are usually defined, for distance metric $d$ and $c>1$ as follows: A family of hash functions is $(r, cr, p_1, p_2)$-LSH ...
44 views

### Are there any continuous-time stochastic processes in which transition probabilities are discontinuous functions over time? [closed]

In stochastic processes, like homogeneous Markov processes, Poisson processes, Queueing systems etc., the functions that represent (transition) probabilities are continuous over time. This is also ...
51 views

### Problem dependent lower bound for stochastic bandits with full information

Suppose you have a $K$ armed stochastic bandit problem but with full information. There are $K$ arms with mean rewards $\mu_1,...,\mu_K$. At each step we have to select an arm, collect the reward from ...
99 views

### Percolation probabilities

I have a finite undirected graph with a probability $p_e$ given for each edge $e$. This gives a random graph by removing each edge e with probability $1-p_e$ independently of the others. I'm ...
139 views

### Maximal correlation vs correlation coefficient when one RV is Gaussian

Last week I asked a question on MOF (see here), but I got no reply. So I am asking my question here. Let a pair of random variables $(X,Y)$ be continuous random variables (i.e., they both have ...
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\}$ (...
117 views

I am reading a paper which is mainly about Dobrushin's contraction coefficient and its generalization. In page 27, the following is defined: Consider an arbitrary, non-negative, convex function $\psi:\... 0answers 764 views ### Time-inhomogeneous Markov Chains I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time. All textbooks and lecture notes I could find initially introduce ... 0answers 56 views ### What is entropy of a variable described by Knightian uncertainty? Given a discrete variable whose value is characterized by Knightian uncertainty, that is, belief and plausibility, as in Dempster-Shafer theory, what is its entropy? 0answers 165 views ### Distribution of number of unique items in a sample Suppose we're sampling a discrete random variable from a distribution f, n times. Is there a simple analytical formulation for the expected number of unique items we obtain, or for the distribution of ... 0answers 243 views ### application for the Kchinchine inequality in Computer Science The classical Kchinchine inequality states that for vector$a=(a_1, \ldots, a_{2m})\in R^{2m}$, for$p\geq 2$, and for independent Rademacher random variables$r_1, \ldots, r_{2m}$, one has $$E(|\... 1answer 271 views ### is it by Chebychev's inequality? [closed] Let x be random variables with mean zero and variance 1. Let n be natural number, t>0, C>0. Let also P(x^2\geq n)\geq C/(n^t). Show, if t\geq4, then P(x^2\geq n)\leq C/(n^2). I got so fare, ... 1answer 227 views ### Proving properties of Random Graphs 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 ... 1answer 79 views ### Does this pairwise independent random process have expected max load \sqrt{n}? This is an extension to the question about balls into bins: Example of pairwise independent random process with expected max load \sqrt{n} . There the following question is asked and answered in ... 2answers 136 views ### Determining the distribution of results of a simple algorithm Setting Consider repeating the following process on the numbers N=\{1, 2, 3, \ldots, n\}: Pick an integer k \in N, uniformly at random. Pick a subset of k elements from N, uniformly at random.... 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 ... 1answer 355 views ### Capacity planning algorithm resources Let's say I have a machine with many boxes of different sizes. I want to put packages inside those boxes. Packages arrive at different time and then stay in the box for specific period of time. I need ... 0answers 42 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 ... 0answers 35 views ### Delaunay Triangulaition (or Voronoi) for a specific distribution of points I found a paper about Delaunay triangulation for a set of points that are distributed by the Poisson distribution (https://pdfs.semanticscholar.org/9693/4b7e8e5483893f4874d7ba6afd812bbfe0ba.pdf). The ... 0answers 33 views ### Expected size of the min-cut, under edge perturbations Suppose we have a graph G(V, E). Assume that the min-cut of this graph is given C=(A/B) and denote the size of the cut with |C|. Create a random modification of the graph: Drop each ... 1answer 343 views ### Bounding Rademacher Averages, with and without chaining One can bound the Rademacher average R_n(A) of a finite set of vectors A\subseteq\{0,1\}^n using Massart's Finite Lemma:$$ R_n(A)\le \max_{a\in A}\|a\|\frac{\sqrt{2\ln|A|}}{n}$$where$\|\cdot\|$... 0answers 46 views ### Establishing causality under conditions of certainty I'm currently reading "Causality: Models, Reasoning, and Inference" by Judea Pearl. Early on, he states that the development assumes that there are no certain entailments, no 1 or 0 probabilities -- ... 1answer 86 views ### Issue in understanding conditional likelihood for a producton rule The Equation1 in paper in link explains how to assign probability to a production rule. Fig1 explains with an example. Now, I have a problem in understanding how to work with this formula since it ... 1answer 48 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 (... 1answer 150 views ### Application of the inequality with expectations Let$\Vert\cdot\Vert$is a norm in$R^n$. Let$x_1,\dots,x_N$non-independent Rademacher random variables random variables (variables which are uniform on$\{-1, 1\}$). . By$E$we denote an ... 1answer 96 views ### Required sample size to hit certain subset of a ground set Suppose$X$is a set of$n$points in$\mathbb{R}^d$and$N_1,\cdots,N_k$are k disjoint (unknown)subsets of$X$. There is a probability distribution$\phi$on$X$defined as$\phi(p) = \frac{\lvert\...
Let a reversible Markov process $m_{t+1}=m_t P$, where $t$ is time that has a stationary distribution $\pi$. I saw in a paper that the dual system was defined as $x_{t+1}=P x_t$. Can anyone give me ...
Say $\sigma_1, \sigma_2, \dots, \sigma_m$ are i.i.d distributed $\pm1$ variables. How do I show that for any choice of $S_1, S_2, \dots, S_d$ subsets of $\{1, 2, \dots, m\}$, the expectation of the ...