Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If you have a stochastic process where you realize a discrete uniform at each i, whats the probability that after realizing $n$ of the dunif R.V.'s, you end up with a certain/particular outcome $a$ being at least as frequent as another particular outcome $b$ (doesn't imply that a and b are the only values the experiment can assume..i.e. not necessarily bernoulli.).\

I'm thinking about visualizing this as a random walk where everytime $a$ occurs I jump ahead and every time $b$ occurs and jump down and any other value I stay. So, the event is basically ending up on one side after n trials (seperating the sides by the point you started at). since its uniform, a and b have the same probabilities and i end up on one side 1/2 the time. not sure if thats sound reasoning.

share|cite|improve this question
I think you are counting the case when the two occur with equal frequency twice in coming up with your $1/2$. If $N_a$ and $N_b$ denote the numbers of occurrences of $a$ and $b$ respectively on the $n$ trials, then shouldn't $P\{N_a > N_b\}$ equal $P\{N_a < N_b\}$ by symmetry? If so, all you need to compute is $P\{N_a = N_b\}$. – Dilip Sarwate Sep 25 '12 at 18:42
thanks. is there an easy way to compute the latter probability? suppose there are 3 equally likely values and we evaluate 10 RV's. – wuschelbeutel Sep 25 '12 at 18:47
What is the discrete uniform defined on? Integers from 1 to n? – Michael Chernick Sep 25 '12 at 22:16
Corrected version of earlier comment: Suppose that the random variable takes on $m$ distinct values. Then, for $0 \leq i \leq \lfloor n/2\rfloor$, $$P\{N_a=N_b=i\}=\frac{n!}{i!i!(n-2i)!}\left(\frac{1}{m}\right)^{2i}\left(\frac{‌​m-2}{m}\right)^{n-2i}.$$ But I am sure there is a much more elegant expression that someone far better versed in probability than I will post fairly soon. – Dilip Sarwate Sep 26 '12 at 2:44
Not much to add to @Dilip's comment, except that the asymptotics are $\sqrt{m/4\pi n}$ when $n\to\infty$ (barring some computation mistakes...). – Did Sep 26 '12 at 6:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.