Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For $1\leq k \leq n+1$, consider the set $S_k$ of functions $f:\{1,\ldots,n\} \rightarrow \{1,\ldots,n+1\}$, with the property that $|f^{-1}\{1,\ldots,k\}| < k$. Note that $|S_1|=n^n$, and $|S_{n+1}| = (n+1)^n$. Is it true that $|S_k|$ grows with $k$?

It's not hard to come up with the formula $$ |S_k| = \sum_{j=0}^{k-1} {n \choose j} k^j (n+1-k)^{n-j}$$ and if you plot this it is at least apparent that the conjecture should be true.

Another vague observation is that, if you divide by $(n+1)^n$ and take limit as $n\rightarrow \infty$, keeping $k$ fixed, you get the expression $$ e^{-k} \sum_{j=0}^{k-1} \frac{k^j}{j!}$$ and using Taylor's integral remainder theorem you can prove the conjecture at least in the limit.

share|improve this question
    
Is this homework? –  Anthony Quas Aug 30 '13 at 15:36
    
No it isn't. Is it really that easy :O? –  funda Aug 30 '13 at 15:42
1  
Have you worked out the formula for $\#S_2$? for $\#S_n$? Have you verified your conjecture numerically for small $n$? If so, please show us the details; if not, there's work you can do before appealing to the crowd. –  Greg Martin Aug 30 '13 at 17:24
1  
This question appears to be off-topic because there is little evidence that the OP gave any thought to it before posting. –  fedja Aug 30 '13 at 19:43
2  
@funda "to not influence other people's train of thought". Most of us here are trained in "ignoring information" (though I admit that it is a non-trivial skill). However, you should remember that the main purpose of this site is to help you out quickly, and the discussion of various approaches to one not so difficult problem is, at best, the secondary purpose. So, the best way to post a question is to state the problem clearly (which you did), and then tell the leads you have and the places where you got stuck (which you didn't) :) –  fedja Aug 31 '13 at 16:27
show 5 more comments

1 Answer

up vote 5 down vote accepted

OK, once I went into "preaching", I feel I am obliged to post a solution too.

Let's consider $n$ i.i.d. Bernoulli variables $X_j$ such that $P(X_j=1)=\frac k{n+1}$ and $P(X_j=0)=1-\frac k{n+1}$. We want to show that the probability of the event $\sum_j X_j<k$ is increasing in $k$. Note that we can model it as $n$ games where the player has $0$ dollars to start with and plays until he either goes down to $-k$ or reaches $n+1-k$. The problem asks to show that the probability to win less than $k$ games increases as $k$ goes up from $1$ to $n$.

Let us play each game until we reach either $n-k$ or $-k$ and then take a short break to look around. Let $P_m$ be the probability that at this moment $m$ games out of $n$ are in the position $n-k$. Assume that we are playing up to $-k$ and $n+1-k$. Then if we are at $-k$ already, it is a sure loss. If we are at $n-k$, it is still uncertain. Thus, the probability we are interested in for $k$, is $$ \sum_{m<k}P_m+\sum_{m\ge k}P_m Q(m\to <k) $$ where $Q(m\to<k)$ is the probability to go from the position with $m$ "almost won" games to that with $<k$ really won games. Similarly, if we are playing up to $-(k+1)$ and $n-k$, the probability in question is $$ 1-\sum_{m>k}P_m-\sum_{m\le k}P_m Q(m\to>k) $$ Thus, the first probability is less than the second iff $$ P_k>\sum_{m\ge k}P_m Q(m\to <k)+\sum_{m\le k}P_m Q(m\to>k) $$ Note now that $P_m<P_k$ for $k\ne m$. Thus, it will suffice to show that $$ \sum_{m\ge k}Q(m\to <k)+\sum_{m\le k}Q(m\to>k)\le 1 $$ The probability to get the unexpected outcome of an almost finished game is $\frac{1}{n+1}$. Thus, this sum can be rewritten as $$ \sum_{u=0}^{n-k} P\left(\sum_{j=1}^{k+u}Y_j\ge u+1\right)+\sum_{u=0}^k P\left(\sum_{j=1}^{n-k+u}Y_j\ge u+1\right) $$ where $Y_j$ are independent Bernoulli with $P(Y_j=1)=\frac{1}{n+1}$. Thus, it will suffice to show that $$ \sigma_s=\sum_{u=0}^\infty P\left(\sum_{j=1}^{s+u}Y_j\ge u+1\right)\le \frac sn $$ However, this is an identity. I'll just prove it by induction in $s$. The base $s=0$ is obvious. Now, conditioning upon the length $\ell$ of the initial streak of $1$'s in the sequence $Y_j$, we have $$ \sigma_{s+1}=\sum_{\ell\ge 0}\left(\frac 1{n+1}\right)^\ell\frac{n}{n+1}(\ell+\sigma_s)=\frac 1n+\sigma_s $$ because when $s\ge 1$, the conditional probability $P\left(\sum_{j=1}^{s+u}Y_j\ge u+1\mid Y_1=\dots=Y_\ell=1,Y_{\ell+1}=0\right)$ equals $1$ if $u\le\ell-1$ and $P\left(\sum_{j=\ell+2}^{s+u}Y_j\ge (u-\ell)+1\right)=P\left(\sum_{j=1}^{(s-1)+(u-\ell)}Y_j\ge (u-\ell)+1\right)$ for $u\ge\ell$.

share|improve this answer
    
This looks great, except I can't figure out why $P_m < P_k$ for $m \neq k$. Thanks! –  funda Sep 2 '13 at 4:32
    
This is just a general property of binomial distributions (the probability to "almost win" is $p=k/n$ and $P_m={n\choose m}p^m(1-p)^{n-m}$). Nothing clever here. –  fedja Sep 2 '13 at 4:44
    
Ah I see, this approach is great, thank you again. It's interesting because the form of the problem was originally a bound on probabilities, but I thought I might be able to come up with an injection between the functions to prove it. –  funda Sep 2 '13 at 4:58
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.