How to estimate velocity in scrum?

The Scrum Guide says nothing about velocity. In fact the word is not used.  My opinion is because it has been so badly used and misrepresented that it is more of a hindrance than a benefit. 

The Merriam-Webster definition of velocity that I think is most applicable is this one

3a: rate of occurrence or action : RAPIDITY 

the velocity of historical change— R. J. Lifton

Too many people will state that velocity is determined by the number of story points completed each Sprint.  However, the concept of Story Points is to provide an estimate (also known as a guess) for the amount of work needed to do something relative to other similar bodies of work based on the information you have at the time you make your guess. In that model, the moment you begin work, the estimates become obsolete as you will learn more and more information that could make the work easier or harder.  So trying to determine your velocity based upon guesses really doesn't make sense to me.

What that customer is actually asking for is some way to understand how predictable you are at delivering valuable bodies of work per Sprint.  That can be done in many ways.  Personally, I prefer to use some Kanban related metrics of throughput, cycle time, aging of work in progress in forecasting the work that is possible.   If your team has never worked together and are on the first iteration of delivering, you honestly have nothing to provide them.  However, if this team has worked together before on other opportunities, you can use their past performance to create some manner of forecast.  I suggest reading the books Actionable Agile Metrics for Predictability and When Will It Be Done by Daniel S Vacanti. The practices suggested in those books have served me well when I am faced with the situation you have.

You won't find anything about velocity in the Scrum Guide. Although it's a relatively common practice among Scrum Teams, the Scrum Guide doesn't require you to estimate Product Backlog Items (beyond trying to ensure that the team believes the work described by one would fit into a single Sprint), use any specific units if you perform estimation, or compute any metrics based on estimations.

If you do want to compute velocity, that is traditionally measured in story points. If you are sizing all of the work that you do in a Sprint in story points, your velocity will just be the number of story points associated with Done Product Backlog Items. You can also do things like take the rolling average over the past few Sprints, as well.

However, I'd question why your client needs to know about your velocity. I've found that velocity is a poor indicator of anything outside the team. Estimation and velocity may be helpful as a planning tool to help the team understand how much work they are likely capable of doing in the Sprint, but it even has some limitations there. I can't think of a valid use that a client would have for this information. It may be worth trying to understand why they want this information or what they are trying to learn and work with them to not only deliver the product and services that you deliver but also information about the product and process quality.

But our client asks us about velocity.

Ask why. Find out why they're interested. Perhaps they've lost a clear line of sight to the value being provided. What does the Product Owner think?

Hi Fatima, 

I don't understand why your client asked for team velocity. It's just the indicator for the team to estimate the amount of tasks they can complete in sprint. It's not a fix number to show as an evidence for team performance.

I think that you want to know how to count the points for user story. So here is what I did. In the meeting, I selected a user story that everyone know how to do it. Showed them to estimate the user story, they needed to know 3 things: complexity, uncertainty, and effort. Then we got agreement on the point of that user story. For example, the given US was count as 2 points. Based on that US, the team knew if the US easier, the point is lower (1 point); if the US more difficult, the point is higher (3 or 5 points). We used Fibonacci. In the first sprint, the team pulled all of USes that they thought they might complete to reach the Spring Goal, then I used those completed US to count for the team velocity at the end of sprint. And continuing using that number of points to forecast for the next sprint. Note that for the same US, 2 or 3 teams can have different points. That's why the velocity shouldn't be used to measure for team performance or to do for anything outside the team. 

Hope it help :) 

Thanks all for insightful response.