Questions tagged [pr.probability]

Questions in probability theory

Filter by
Sorted by
Tagged with
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
0answers
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}$...
2
votes
0answers
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, ...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
2answers
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. ...
1
vote
2answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
94 views

Using a probability distribution in the fooling set technique for communication complexity

I'm reading through the communication complexity book of Kushilevitz and Nisan, and in the section about fooling sets I encountered this proposition: Let $\mu$ be a probability distribution of $X\...
1
vote
1answer
122 views

Average Regret Bounds for Linear Stochastic Bandits

I am reading this paper on linear stochastic bandits : http://papers.nips.cc/paper/4417-improved-algorithms-for-linear-stochastic-bandits.pdf All the results are stated in a high-probability ...
1
vote
1answer
70 views

Terminology for games with incomplete information and no prior beliefs

Can anyone please tell me what is the term used for games with incomplete information and there are no prior beliefs about other players' private information. For example, let $ v_i(a_i,\theta_i) $ ...
1
vote
1answer
82 views

Issue with inequalities involving probablities

I'm reading this paper http://eccc.hpi-web.de/report/2016/044/download/, at page 7 you can see this equation: $$ \sum_t \mathbb{E}_{w \in W} [|p_t - p_{t|w,w}|] = 2 \sum_t \mathbb{E}_{w \in W} [\max(...
1
vote
1answer
106 views

The noise distribution on $F_2^n$: probability of landing in a subspace versus a coset

Let $V = F_2^n$ be the $n$-dimensional vector space over the field of two elements. The $\epsilon$-noise distribution on $V$, denoted $\mu_\epsilon$, is a probability distribution on $V$ for which ...
1
vote
1answer
92 views

Inequality for p-norm of probability distributions

I want to show the following inequality, which seems like it should have an elementary proof (or even a well-known name). Suppose $p, q$ are discrete probability distributions. And suppose that $p_i \...
1
vote
1answer
77 views

How to play the following game? (placing balls into bins)

Let $n,\ell\in\mathbb N$ for some $n\gg \ell\gg 1$. The goal is to pick two sequences of numbers, $x_1,\ldots,x_\ell$ and $y_1,\ldots,y_\ell$ such that $$\Sigma_{i=1}^\ell x_i = n\quad{}\mbox{and}\...
1
vote
1answer
55 views

A theorem regarding statistically-hiding commitment schemes

Let $C_n$ be a non-interactive statistically-hiding commitment scheme, able to commit to an $n$-bit string. To commit to $m \in \{0,1\}^n$, the sender picks a random $r$ (of proper length), and sends $...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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\}$ (...
1
vote
0answers
117 views

Orlicz Norm and a result on expectation

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:\...
1
vote
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 ...
1
vote
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?
1
vote
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 ...
1
vote
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(|\...
0
votes
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, ...
0
votes
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 ...
0
votes
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 ...
0
votes
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....
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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\|$...
0
votes
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 -- ...
-1
votes
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 ...
-1
votes
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 (...
-1
votes
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 ...
-1
votes
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\...
-2
votes
1answer
169 views

Dual of a Reversible Markov Chain [closed]

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 ...
-2
votes
2answers
238 views

Lemma needed for my machine learning research [closed]

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 ...